codeforces1093G Multidimensional Queries 【线段树】

题目分析：
搜索2^k种情况，线段树分别处理就行了，正确性明显。
代码：
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 202000;
 5 
 6 int n,k;
 7 struct node{int x[5];}a[maxn];
 8 
 9 int Tmax[1<<5][maxn*4],Tmin[1<<5][maxn*4];
10 
11 void Modify(int now,int tl,int tr,int dt,int pos){
12     if(tl == tr){
13     int ans = 0;
14     for(int i=0;i<k;i++){
15         if(dt & (1<<i))ans += a[tl].x[i];
16         else ans -= a[tl].x[i];
17     }
18     Tmax[dt][now] = Tmin[dt][now] = ans;
19     }else{
20     int mid = (tl+tr)/2;
21     if(pos <= mid) Modify(now<<1,tl,mid,dt,pos);
22     else Modify(now<<1|1,mid+1,tr,dt,pos);
23     Tmax[dt][now] = max(Tmax[dt][now<<1],Tmax[dt][now<<1|1]);
24     Tmin[dt][now] = min(Tmin[dt][now<<1],Tmin[dt][now<<1|1]);
25     }
26 }
27 
28 void Modifydfs(int now,int dt,int pos){
29     if(now == k) Modify(1,1,n,dt,pos);
30     else{Modifydfs(now+1,dt,pos); Modifydfs(now+1,dt+(1<<now),pos);}
31 }
32 
33 pair<int,int> query(int now,int tl,int tr,int l,int r,int dt){
34     if(tl >= l && tr <= r) return make_pair(Tmax[dt][now],Tmin[dt][now]);
35     if(tl > r || tr < l) return make_pair(-1e9,1e9);
36     int mid = (tl+tr)/2;
37     pair<int,int> a1 = query(now<<1,tl,mid,l,r,dt);
38     pair<int,int> a2 = query(now<<1|1,mid+1,tr,l,r,dt);
39     return make_pair(max(a1.first,a2.first),min(a1.second,a2.second));
40 }
41 
42 int dfs2(int now,int dt,int l,int r){
43     if(now == k) {
44     pair<int,int> ans = query(1,1,n,l,r,dt);
45     return ans.first-ans.second;
46     }else{return max(dfs2(now+1,dt,l,r),dfs2(now+1,dt+(1<<now),l,r));}
47 }
48 
49 void read(){
50     scanf("%d%d",&n,&k);
51     for(int i=1;i<=n;i++){
52     for(int j=0;j<k;j++) scanf("%d",&a[i].x[j]);
53     }
54     for(int i=1;i<=n;i++) Modifydfs(0,0,i);
55 }
56 
57 void work(){
58     int q; scanf("%d",&q);
59     for(int i=1;i<=q;i++){
60     int cas; scanf("%d",&cas);
61     if(cas == 1){
62         int now; scanf("%d",&now);
63         for(int j=0;j<k;j++) scanf("%d",&a[now].x[j]);
64         Modifydfs(0,0,now);
65     }else{
66         int l,r; scanf("%d%d",&l,&r);
67         int maxmum = dfs2(0,0,l,r);
68         printf("%d
",maxmum);
69     }
70     }
71 }
72 
73 int main(){
74     read();
75     work();
76     return 0;
77 }