CF1093G Multidimensional Queries

思路：

参考了https://codeforces.com/blog/entry/63877。主要利用了曼哈顿距离的性质。

实现过程中遇到一个问题：不同的线段树数组的定义方式会导致运行速度很大的差别。tree[800000][32][2]比tree[2][32][800000]快了一倍，从而导致了TLE和AC的区别。可能是程序运行过程中频繁访问不连续的地址导致cache失效。以后如果需要对很大的数组进行频繁操作的话需要注意这一点。

实现：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int N = 200005, K = 5, INF = 0x3f3f3f3f;
  4 int a[N][K], b[K], tree[N * 4][1 << K][2], n, k;
  5 
  6 void build(int num, int l, int r)
  7 {
  8     if (l == r)
  9     {
 10         for (int i = 0; i < (1 << k); i++)
 11         {
 12             int sum = 0;
 13             for (int d = 0; d < k; d++)
 14             {
 15                 if ((i >> d) & 1) sum += a[l][d];
 16                 else sum -= a[l][d];
 17             }
 18             tree[num][i][0] = tree[num][i][1] = sum;
 19         }
 20         return;
 21     }
 22     int m = l + r >> 1;
 23     build(num << 1, l, m);
 24     build(num << 1 | 1, m + 1, r);
 25     for (int i = 0; i < (1 << k); i++)
 26     {
 27         tree[num][i][1] = max(tree[num << 1][i][1], tree[num << 1 | 1][i][1]);
 28         tree[num][i][0] = min(tree[num << 1][i][0], tree[num << 1 | 1][i][0]);
 29     }
 30 }
 31 
 32 void update(int num, int l, int r, int x)
 33 {
 34     if (l == r)
 35     {
 36         for (int i = 0; i < (1 << k); i++)
 37         {
 38             int sum = 0;
 39             for (int d = 0; d < k; d++)
 40             {
 41                 if ((i >> d) & 1) sum += b[d];
 42                 else sum -= b[d];
 43             }
 44             tree[num][i][0] = tree[num][i][1] = sum;
 45         }
 46         return;
 47     }
 48     int m = l + r >> 1;
 49     if (x <= m) update(num << 1, l, m, x);
 50     else update(num << 1 | 1, m + 1, r, x);
 51     for (int i = 0; i < (1 << k); i++)
 52     {
 53         tree[num][i][1] = max(tree[num << 1][i][1], tree[num << 1 | 1][i][1]);
 54         tree[num][i][0] = min(tree[num << 1][i][0], tree[num << 1 | 1][i][0]);
 55     }
 56 }
 57 
 58 int query(int num, int l, int r, int x, int y, int t, int id)
 59 {
 60     if (x <= l && y >= r) return tree[num][id][t];
 61     if (y < l || x > r) return t ? -INF : INF;
 62     int m = l + r >> 1, ans = t ? -INF : INF;
 63     if (x <= m)
 64     {
 65         if (t) ans = max(ans, query(num << 1, l, m, x, y, t, id));
 66         else ans = min(ans, query(num << 1, l, m, x, y, t, id));
 67     }
 68     if (y >= m + 1)
 69     {
 70         if (t) ans = max(ans, query(num << 1 | 1, m + 1, r, x, y, t, id));
 71         else ans = min(ans, query(num << 1 | 1, m + 1, r, x, y, t, id));
 72     }
 73     return ans;
 74 }
 75 
 76 int main()
 77 {
 78     int q, t, x, l, r;
 79     scanf("%d %d", &n, &k);
 80     for (int i = 1; i <= n; i++)
 81         for (int j = 0; j < k; j++)
 82             scanf("%d", &a[i][j]);
 83     build(1, 1, n);
 84     scanf("%d", &q);
 85     while (q--)
 86     {
 87         scanf("%d", &t);
 88         if (t == 1)
 89         {
 90             scanf("%d", &x);
 91             for (int i = 0; i < k; i++) scanf("%d", &b[i]);
 92             update(1, 1, n, x);
 93         }
 94         else
 95         {
 96             scanf("%d %d", &l, &r);
 97             int ans = -INF;
 98             for (int i = 0; i < (1 << k); i++)
 99             {
100                 int maxn = query(1, 1, n, l, r, 1, i);
101                 int minn = query(1, 1, n, l, r, 0, i);
102                 ans = max(ans, maxn - minn);
103             }
104             printf("%d
", ans);
105         }
106     }
107     return 0;
108 }