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_2cdots b_k)，表示将 (a_i) 修改为 ((b_1,b_2,cdots,b_k)) 。
- (2 l r)，表示询问 ([l,r]) 内最大的两点间曼哈顿距离，即任取 (x,yin[l,r]) 得到的所有曼哈顿距离中的最大值。
(n,mleq 2cdot 10^5,kleq 5)
Solution
比较套路的一道题吧...然而比赛时确实没有想出来
看见曼哈顿距离就想着把绝对值拆出来，先拿二维的举例子：
(egin{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]))
跟二进制扯上关系了，再去看一眼数据范围发现 (kleq 5) ，线段树每个节点维护 (2^k) 个值即可。
Code
#include<bits/stdc++.h>
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<int,int>
#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,qr
int 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<k;j++){
if(i>>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<k;j++){
if(i>>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<qr) ans=ans+query(rss);
return ans;
}
signed main(){
n=getint(),k=getint();maxn=(1<<k)-1;
for(int i=1;i<=n;i++)
for(int j=0;j<k;j++) val[i][j]=getint();
build(1,1,n);
m=getint();
while(m--){
if(getint()==1){
int pos=getint();
for(int i=0;i<k;i++) val[pos][i]=getint();
modify(1,1,n,pos);
} else{
int l=getint(),r=getint();
Node ans=query(1,1,n,l,r);
int ppp=-1e9;
for(int i=0;i<=maxn;i++) ppp=max(ppp,ans.a[i]+ans.a[i^maxn]);
printf("%d
",ppp);
}
} return 0;
}