题目链接：
/contest/1093/problem/G
题目：
题意：
在k维空间中有n个点，每次给你两种操作，一种是将某一个点的坐标改为另一个坐标，一种操作是查询[l,r]中曼哈顿距离最大的两个点的最大曼哈顿距离。
思路：
对于曼哈顿距离，我们将其绝对值去掉会发现如下规律（以二维为例）：
故这题我们可以用线段树来维护[l,r]中上述每种情况的最大值和最小值，用二进制来枚举xy的符号（1为正，0为负），最后答案是 每种情况中区间最大值-区间最小值 的最大值。
代码实现如下：
1 #include <set> 2 #include <map> 3 #include <deque> 4 #include <queue> 5 #include <stack> 6 #include <cmath> 7 #include <ctime> 8 #include <bitset> 9 #include <cstdio> 10 #include <string> 11 #include <vector> 12 #include <cstdlib> 13 #include <cstring> 14 #include <iostream> 15 #include <algorithm> 16 using namespace std; 17 18 typedef long long LL; 19 typedef pair<LL, LL> pLL; 20 typedef pair<LL, int> pli; 21 typedef pair<int, LL> pil;; 22 typedef pair<int, int> pii; 23 typedef unsigned long long uLL; 24 25 #define lson rt<<1 26 #define rson rt<<1|1 27 #define lowbit(x) x&(-x) 28 #define name2str(name) (#name) 29 #define bug printf("*********\n") 30 #define debug(x) cout<<#x"=["<<x<<"]" <<endl 31 #define FIN freopen("D://code//in.txt", "r", stdin) 32 #define IO ios::sync_with_stdio(false),cin.tie(0) 33 34 const double eps = 1e-8; 35 const int mod = 1000000007; 36 const int maxn = 2e5 + 7; 37 const double pi = acos(-1); 38 const int inf = 0x3f3f3f3f; 39 const LL INF = 0x3f3f3f3f3f3f3f3fLL; 40 41 int n, k, q, op, x, l, r; 42 int a[maxn][10], num[10]; 43 44 struct node { 45int l, r, mx, mn; 46 }segtree[maxn<<2][33]; 47 48 void push_up(int rt, int pp) { 49segtree[rt][pp].mx = max(segtree[lson][pp].mx, segtree[rson][pp].mx); 50segtree[rt][pp].mn = min(segtree[lson][pp].mn, segtree[rson][pp].mn); 51 } 52 53 void build(int rt, int l, int r, int pp) { 54segtree[rt][pp].l = l, segtree[rt][pp].r = r; 55segtree[rt][pp].mx = segtree[rt][pp].mn = 0; 56if(l == r) { 57 for(int i = 0; i < k; i++) { 58 if(pp & (1<<i)) { 59 segtree[rt][pp].mx += a[l][i]; 60 segtree[rt][pp].mn += a[l][i]; 61 } else { 62 segtree[rt][pp].mx -= a[l][i]; 63 segtree[rt][pp].mn -= a[l][i]; 64 } 65 } 66 return; 67} 68int mid = (l + r) >> 1; 69build(lson, l, mid, pp); 70build(rson, mid + 1, r, pp); 71push_up(rt, pp); 72 } 73 74 void update(int rt, int pos, int pp) { 75if(segtree[rt][pp].l == segtree[rt][pp].r) { 76 segtree[rt][pp].mx = segtree[rt][pp].mn = 0; 77 for(int i = 0; i < k; i++) { 78 if(pp & (1<<i)) { 79 segtree[rt][pp].mx += num[i]; 80 segtree[rt][pp].mn += num[i]; 81 } else { 82 segtree[rt][pp].mx -= num[i]; 83 segtree[rt][pp].mn -= num[i]; 84 } 85 } 86 return; 87} 88int mid = (segtree[rt][pp].l + segtree[rt][pp].r) >> 1; 89if(pos <= mid) update(lson, pos, pp); 90else update(rson, pos, pp); 91push_up(rt, pp); 92 } 93 94 int query(int rt, int l, int r, int pp, int op) { 95if(segtree[rt][pp].l >= l && segtree[rt][pp].r <= r) { 96 if(op == 1) { 97 return segtree[rt][pp].mx; 98 } else { 99 return segtree[rt][pp].mn;100 }101}102int mid = (segtree[rt][pp].l + segtree[rt][pp].r) >> 1;103if(r <= mid) return query(lson, l, r, pp, op);104else if(l > mid) return query(rson, l, r, pp, op);105else {106 if(op == 1) return max(query(lson, l, mid, pp, op), query(rson, mid + 1, r, pp, op));107 else return min(query(lson, l, mid, pp, op), query(rson, mid + 1, r, pp, op));108}109 }110 111 int main(){112 #ifndef ONLINE_JUDGE113FIN;114 #endif115scanf("%d%d", &n, &k);116for(int i = 1; i <= n; i++) {117 for(int j = 0; j < k; j++) {118 scanf("%d", &a[i][j]);119 }120}121for(int i = 0; i < (1<<k); i++) {122 build(1, 1, n, i);123}124scanf("%d", &q);125while(q--) {126 scanf("%d", &op);127 if(op == 1) {128 scanf("%d", &x);129 for(int i = 0; i < k; i++) {130 scanf("%d", &num[i]);131 }132 for(int i = 0; i <(1<<k); i++) {133 update(1, x, i);134 }135 } else {136 scanf("%d%d", &l, &r);137 int mx = -inf;138 for(int i = 0; i < (1<<k); i++) {139 mx = max(mx, query(1, l, r, i, 1) - query(1, l, r, i, 2));140 }141 printf("%d\n", mx);142 }143}144return 0;145 }
