题意
给出n(n<=2E5)个k(k<=5)维空间中的点，每次询问[l,r]中两个点曼哈顿距离的最大值（可以类比二维）
思考
根据初中数学，我们知道
。
而每个维度上的曼哈顿距离是独立的。
k又很小，因此我们可以一股脑地分类讨论，把所有可能的结果算出来。
设f[S]表示k位二进制下k个维度的正负情况，如k=3时,(2,3,3)对应S(2)=110的结果为2+2-3。
每次枚举S的所有情况，一股脑塞进去就行了！最后的结果就是max{f[i]+f[2^k-i-1]}。
为什么是对的？因为这求的是最大值，所有可能的情况中电脑会机械化地算出最大可能的结果。
简单线段树维护。
代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2E5+5; 4 int n,k,m,a[maxn][6]; 5 struct tree{int l,r,f[32];}t[maxn*4]; 6 tree merge(tree x,tree y) 7 { 8 tree z; 9 z.l=x.l,z.r=y.r; 10 for(int i=0;i<(1<<k);++i)z.f[i]=max(x.f[i],y.f[i]); 11 return z; 12 } 13 void get(int x,int num) 14 { 15 for(int i=0;i<(1<<k);++i) 16 { 17 int sum=0; 18 for(int j=0;j<k;++j) 19 { 20 if(i&(1<<j))sum+=a[x][j]; 21 else sum-=a[x][j]; 22 } 23 t[num].f[i]=sum; 24 } 25 } 26 void build(int l,int r,int num) 27 { 28 t[num].l=l;t[num].r=r; 29 if(l==r) 30 { 31 get(l,num); 32 return; 33 } 34 int mid=(l+r)>>1; 35 build(l,mid,num*2);build(mid+1,r,num*2+1); 36 t[num]=merge(t[num*2],t[num*2+1]); 37 } 38 void change(int pos,int num) 39 { 40 if(t[num].l==t[num].r) 41 { 42 get(pos,num); 43 return; 44 } 45 int mid=(t[num].l+t[num].r)>>1; 46 if(pos<=mid)change(pos,num*2); 47 else change(pos,num*2+1); 48 t[num]=merge(t[num*2],t[num*2+1]); 49 } 50 tree ask(int L,int R,int num) 51 { 52 if(L<=t[num].l&&t[num].r<=R)return t[num]; 53 int mid=(t[num].l+t[num].r)>>1; 54 if(R<=mid)return ask(L,R,num*2); 55 else if(mid<L)return ask(L,R,num*2+1); 56 else return merge(ask(L,R,num*2),ask(L,R,num*2+1)); 57 } 58 int main() 59 { 60 ios::sync_with_stdio(false); 61 cin>>n>>k; 62 for(int i=1;i<=n;++i) 63 for(int j=0;j<k;++j)cin>>a[i][j]; 64 cin>>m; 65 build(1,n,1); 66 while(m--) 67 { 68 int opt,x; 69 cin>>opt; 70 if(opt==1) 71 { 72 cin>>x; 73 for(int j=0;j<k;++j)cin>>a[x][j]; 74 change(x,1); 75 } 76 else 77 { 78 int l,r,ans=0; 79 cin>>l>>r; 80 tree u=ask(l,r,1); 81 for(int i=0;i<(1<<k);++i)ans=max(ans,u.f[i]+u.f[(1<<k)-i-1]); 82 cout<<ans<<endl; 83 } 84 } 85 return 0; 86 }
CF1093G [Multidimensional Queries]
原文：https://www.cnblogs.com/GreenDuck/p/10554772.html
