Description

给你 \(n\) 个 \(k\) 维的点 \(a_{1..n}\)，定义两点\((x_1,x_2,\cdots,x_k),(y_1,y_2,\cdots,y_k)\)间的曼哈顿距离为 \(\sum_{i=1}^k|x_i-y_i|\) 。

你需要执行下面两种操作：

• \(1\ i\ b_1\ b_2\cdots b_k\)，表示将 \(a_i\) 修改为 \((b_1,b_2,\cdots,b_k)\) 。
• \(2\ l\ r\)，表示询问 \([l,r]\) 内最大的两点间曼哈顿距离，即任取 \(x,y\in[l,r]\) 得到的所有曼哈顿距离中的最大值。

\(n,m\leq 2\cdot 10^5,k\leq 5\)

Solution

比较套路的一道题吧...然而比赛时确实没有想出来

看见曼哈顿距离就想着把绝对值拆出来，先拿二维的举例子：

\(\begin{align}& |x_1-y_1|+|x_2-y_2|\\&=\max(x_1-y_1,y_1-x_1)+\max(x_2-y_2,y_2-x_2)\\&=\max(x_1-y_1+x_2-y_2,x_1-y_1+y_2-x_2,y_1-x_1+x_2-y_2,y_1-x_1+y_2-x_2)\end{align}\)

如果我们设 \(s[x][0]=x_1+x_2,s[x][1]=-x_1+x_2,s[x][2]=x_1-x_2,s[x][3]=-x_1-x_2\)

那么这个式子就等于\(\max(s[x][0]+s[y][3],s[x][1]+s[y][2],s[x][2]+s[y][1],s[x][3]+s[y][0])\)

跟二进制扯上关系了，再去看一眼数据范围发现 \(k\leq 5\) ，线段树每个节点维护 \(2^k\) 个值即可。

Code

#include
    
     using std::min;using std::max;using std::swap;using std::vector;typedef double db;typedef long long ll;#define pb(A) push_back(A)#define pii std::pair
     
      #define all(A) A.begin(),A.end()#define mp(A,B) std::make_pair(A,B)const int K=33;const int N=2e5+5;#define ls x<<1#define rs x<<1|1#define lss ls,l,mid,ql,qr#define rss rs,mid+1,r,ql,qrint n,k,m,maxn,val[N][6];struct Node{    int a[K];    Node(){memset(a,0xcf,sizeof a);}    friend Node operator+(Node x,Node y){        Node z;        for(int i=0;i<=maxn;i++) z.a[i]=max(x.a[i],y.a[i]);        return z;    }}sum[N<<2];int getint(){    int X=0,w=0;char ch=getchar();    while(!isdigit(ch))w|=ch=='-',ch=getchar();    while( isdigit(ch))X=X*10+ch-48,ch=getchar();    if(w) return -X;return X;}void pushup(int x){    sum[x]=sum[ls]+sum[rs];}void build(int x,int l,int r){    if(l==r){        for(int i=0;i<=maxn;i++){            sum[x].a[i]=0;            for(int j=0;j
      
       >j&1) sum[x].a[i]+=val[l][j];                else sum[x].a[i]-=val[l][j];            }        } return;    } int mid=l+r>>1;    build(ls,l,mid),build(rs,mid+1,r);    pushup(x);}void modify(int x,int l,int r,int ql){    if(l==r){        for(int i=0;i<=maxn;i++){            sum[x].a[i]=0;            for(int j=0;j
       
        >j&1) sum[x].a[i]+=val[l][j];                else sum[x].a[i]-=val[l][j];            }        } return;    } int mid=l+r>>1;    ql<=mid?modify(ls,l,mid,ql):modify(rs,mid+1,r,ql);    pushup(x);}Node query(int x,int l,int r,int ql,int qr){    if(ql<=l and r<=qr) return sum[x];    int mid=l+r>>1;Node ans;    if(ql<=mid) ans=ans+query(lss);    if(mid