前言
DennyQi太巨了!
定义一个点(a)，(a_x)表示(a)在第(x)维空间上的坐标值
题解
这题的思路珂以说非常巧妙(原谅我又用了这个"珂")，
我们知道曼哈顿距离是(sum|a_i-b_i|)，(|a_i-b_i|)其实也珂以看作是((a_i-b_i))和((b_i-a_i))中较大的那个。
根据上面的分析曼哈顿距离珂以看作是(sum max(a_i-b_i,b_i-a_i))，
继续分析珂以得出，每个点在每一维度上要应用的无非只有两种情况(a_i)，(-a_i)。
由于区间内取两点求最小值要求每个点都是完整的(就是说一旦选取了该点那么必定会用到该点所有维度上的坐标)，那么也就意味着对于一个点，它最多可能(仅为可能)用到的状态会是(2^k)次方个。
本题坐标只有5维，电脑不是人脑，那么显然我们珂以枚举解决以上问题。
那么求曼哈顿距离的时候便利所有(a_i)的正负性，显然若(a_i)为正，(b_i)即负；(a_i)为负，(b_i)为正。
如果用一个二进制状态来压缩，1表示(a_i)为正，0表示(a_i)为负，显然任意一组关于(a)的状态，记为(sta)，
对应的(b)的装态表示为((((2^k) - 1) - sta))也珂以记作((((2^k) - 1) extbf{xor} sta))。
那么用一个线段树维护，每一个节点表示对应的区间([l,r])内的曼哈顿距离最大值。
上传标记非常简单就是暴力取两个子节点，然后取对于每一种正负性的珂能，都取max即可。
inline void pushUp(int pos){
for (int i = 0; i < max_sta; ++i)
seg[pos].f[i] = max(seg[pos << 1].f[i], seg[pos << 1 | 1].f[i]);
}
同理应用于合并query时的左右子树的结果。
例子
如果您没有看懂上面的文字，我们不妨来举一个例子。
若(k=3)时有两个点(a,b)坐标分别记为((1,2,3),(-1,2,4))
那么对于点a来说有(2^3=8)种状态，
即((1,2,3),(1,2,-3),(1,-2,3),(1,-2,-3),)
((-1,2,3),(-1,2,-3),(-1,-2,3),(-1,-2,-3))
同理b也有(2^3=8)种状态，对于这(a,b)的(8)种状态两两对应，也就是
((1,2,3))对应((-(-1),-2,-4)dots)这些互相对应的状态取max以后也就是 (sum|a_i-b_i|)啦QAQ
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Pos{
int f[32];
} seg[800005];
int n, k, max_sta;
inline void pushUp(int pos){
for (int i = 0; i < max_sta; ++i)
seg[pos].f[i] = max(seg[pos << 1].f[i], seg[pos << 1 | 1].f[i]);
}
int tmppos[5];
void build(int pos, int l, int r){
if (l == r){
for (int i = 0; i < k; ++i) scanf("%d", &tmppos[i]);
for (int i = 0; i < max_sta; ++i){
seg[pos].f[i] = 0;
for (int j = 0; j < k; ++j)
if (i & (1 << j))
seg[pos].f[i] += tmppos[j];
else
seg[pos].f[i] -= tmppos[j];
}
return ;
}
int mid = (l + r) >> 1;
build(pos << 1, l, mid), build(pos << 1 | 1, mid + 1, r);
pushUp(pos);
}
inline void mrg(Pos &a, Pos b){
for (int i = 0; i < max_sta; ++i)
a.f[i] = max(a.f[i], b.f[i]);
}
Pos query(int pos, int l, int r, int x, int y){
if (x <= l && r <= y) return seg[pos];
int mid = (l + r) >> 1;
Pos res;
if (x <= mid)
res = query(pos << 1, l, mid, x, y);
if (y > mid){
if (x <= mid)
mrg(res, query(pos << 1 | 1, mid + 1, r, x, y));
else
res = query(pos << 1 | 1, mid + 1, r, x, y);
}
return res;
}
void modify(int pos, int l, int r, int x){
if (l == r){
for (int i = 0; i < max_sta; ++i){
seg[pos].f[i] = 0;
for (int j = 0; j < k; ++j)
if (i & (1 << j))
seg[pos].f[i] += tmppos[j];
else
seg[pos].f[i] -= tmppos[j];
}
return ;
}
int mid = (l + r) >> 1;
if (x <= mid) modify(pos << 1, l, mid, x);
else modify(pos << 1 | 1, mid + 1, r, x);
pushUp(pos);
}
int main(){
scanf("%d %d", &n, &k); max_sta = 1 << k;
build(1, 1, n);
int q; scanf("%d", &q);
while (q--){
int op; scanf("%d", &op);
int i;
if (op == 1){
scanf("%d", &i);
for (int j = 0; j < k; ++j)
scanf("%d", &tmppos[j]);
modify(1, 1, n, i);
}
else if (op == 2){
int l, r; scanf("%d %d", &l, &r);
Pos res = query(1, 1, n, l, r);
int ans = 0;
for (int i = 0; i < (1 << (k - 1)); ++i)
ans = max(ans, res.f[i] + res.f[(max_sta - 1) ^ i]);
printf("%d
", ans);
}
}
return 0;
}