CF 1093 G. Multidimensional Queries

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

G. Multidimensional Queries

链接

分析：

考虑如何去掉绝对值符号。

$\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$，由于k比较小，考虑枚举每一维的符号，发现如果不是最终的答案，结果会变小，不影响取max的操作。

然后就是单点修改，区间查询最大最小值。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<cctype>

 #include<set>

 #include<queue>

 #include<vector>

 #include<map>

 #define Root 1, n, 1

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 struct Node{ int x[]; }A[N];

 struct Que{ int opt, x[], l, r; }Q[N];

 int ans[N];

 struct SegmentTree{

     int mx[N << ], mn[N << ];

     void update(int l,int r,int rt,int p,int x) {

         if (l == r) { mn[rt] = mx[rt] = x; return; }

         int mid = (l + r) >> ;

         if (p <= mid) update(lson, p, x);

         else update(rson, p, x);

         mx[rt] = max(mx[rt << ], mx[rt <<  | ]);

         mn[rt] = min(mn[rt << ], mn[rt <<  | ]);

     }

     int query_min(int l,int r,int rt,int L,int R) {

         if (L <= l && r <= R) return mn[rt];

         int mid = (l + r) >> ;

         if (R <= mid) return query_min(lson, L, R);

         else if (L > mid) return query_min(rson, L, R);

         else return min(query_min(lson, L, R), query_min(rson, L, R));

     }

     int query_max(int l,int r,int rt,int L,int R) {

         if (L <= l && r <= R) return mx[rt];

         int mid = (l + r) >> ;

         if (R <= mid) return query_max(lson, L, R);

         else if (L > mid) return query_max(rson, L, R);

         else return max(query_max(lson, L, R), query_max(rson, L, R));

     }

 }T;

 int main() {

     int n = read(), k = read();

     for (int i = ; i <= n; ++i)

         for (int j = ; j < k; ++j) A[i].x[j] = read();

     int m = read();

     for (int i = ; i <= m; ++i) {

         Q[i].opt = read(); Q[i].r = -;

         if (Q[i].opt == ) {

             Q[i].l = read();

             for (int j = ; j < k; ++j) Q[i].x[j] = read();

         }

         else {

             Q[i].l = read(), Q[i].r = read();

         }

     }

     int S = ( << k) - , now;

     for (int s = ; s <= S; ++s) {

         for (int i = ; i <= n; ++i) {

             now = ;

             for (int j = ; j < k; ++j) now += ((s >> j) & ) ? (A[i].x[j]) : (-A[i].x[j]);

             T.update(Root, i, now);

         }

         for (int i = ; i <= m; ++i) {

             if (Q[i].opt == ) {

                 int mn = T.query_min(Root, Q[i].l, Q[i].r);

                 int mx = T.query_max(Root, Q[i].l, Q[i].r);

                 ans[i] = max(ans[i], mx - mn);

             }

             else {

                 now = ;

                 for (int j = ; j < k; ++j) now += ((s >> j) & ) ? (Q[i].x[j]) : (-Q[i].x[j]);

                 T.update(Root, Q[i].l, now);

             }

         }

     }

     for (int i = ; i <= m; ++i) {

         if (Q[i].r == -) continue;

         printf("%d\n", ans[i]);

     }

     return ;

 }