Codeforces 1093G
题意)：给你 $n$ 个 $k$ 维的点 $a_{1..n}$，定义两点$(x_1,x_2,\cdots,x_k),(y_1,y_2,\cdots,y_k)$间的曼哈顿距离为 $\sum_{i=1}^k|x_i-y_i|$。
你需要执行下面两种操作：
$1 i b_1 b_2\cdots b_k$，表示将 $a_i$修改为 $(b_1,b_2,\cdots,b_k)$。
$2 l r$，表示询问 $[l,r]$ 内最大的两点间曼哈顿距离，即任取 $x,y\in[l,r]$ 得到的所有曼哈顿距离中的最大值。
翻译来自Luogu
对于绝对值式子，不好处理我们作一个变式。
考虑二维的情况，设点$(a_1, a_2), (b_1, b_2)$，则根据绝对值函数定义和$x \leq |x|$，有
$$
|a_1-b_1|+|a_2-b_2| \\
= \max (a_1-b_1, b_1-a_1)+ \max (a_2-b_2, b_2-a_2) \\
= \max (a_1-b_1+a_2-b_2, a_1-b_1+b_2-a_2, b_1-a_1+a_2-b_2, b_1-a_1+b_2-a_2) \\
= \max ((a_1+a_2)-(b_1+b_2), (a_1-a_2)-(b_1-b_2), (-a_1+a_2)-(-b_1+b_2), (-a_1-a_2)-(-b_1-b_2))
$$
观察到符号是+和-的$2^d$种不同组合，所以我们设第$i$个点的第$j$种为$s(i,j)$，那么两点曼哈顿距离最大值就是
$$
\max_j \max_i(s(i,j)-s(i,j))
$$
变形得
$$
\max_j (\max_i(s(i,j))-\min_i(s(i,j)))
$$
那么用线段树维护$\max_is(i,j)$和$\min_is(i,j)$即可。
知识点：
以后遇到绝对值$\max \min$式子要尝试拆一下，因为很多这样的式子是不方便直接处理的，要转化一下。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 200000 + 5;
const LL INF = 3223372036854775808ll;
int n, k, q, inp[10];
LL s[40], retmax[40], retmin[40];
#define M ((l + r) >> 1)
#define lc (o << 1)
#define rc (o << 1 | 1)
LL maxv[MAXN * 4][40], minv[MAXN * 4][40];
void pushup(int o) {
for (int i = 0; i <= 32; ++i) maxv[o][i] = max(maxv[lc][i], maxv[rc][i]);
for (int i = 0; i <= 32; ++i) minv[o][i] = min(minv[lc][i], minv[rc][i]);
}
void build(int o, int l, int r) {
if (l == r) {
for (int i = 0; i <= 32; ++i) maxv[o][i] = -INF;
for (int i = 0; i <= 32; ++i) minv[o][i] = INF;
} else {
build(lc, l, M), build(rc, M + 1, r);
pushup(o);
}
}
void update(int o, int l, int r, int p) {
if (l == r) {
for (int i = 0; i <= 32; ++i) maxv[o][i] = s[i];
for (int i = 0; i <= 32; ++i) minv[o][i] = s[i];
return ;
}
if (p <= M) update(lc, l, M, p);
else if (M < p) update(rc, M + 1, r, p);
pushup(o);
}
void query(int o, int l, int r, int x, int y) {
if (x <= l && r <= y) {
for (int i = 0; i <= 32; ++i) retmax[i] = max(retmax[i], maxv[o][i]);
for (int i = 0; i <= 32; ++i) retmin[i] = min(retmin[i], minv[o][i]);
return ;
}
if (x <= M) query(lc, l, M, x, y);
if (M < y) query(rc, M + 1, r, x, y);
}
void clean() {
}
int solve() {
clean();
scanf("%d%d", &n, &k);
build(1, 1, n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) scanf("%d", &inp[j]);
ms(s, 0);
for (int S = 0; S < (1 << k); ++S) {
for (int j = 1; j <= k; ++j) {
s[S] += ((S & (1 << (j - 1))) ? 1ll : -1ll) * inp[j];
}
}
update(1, 1, n, i);
}
scanf("%d", &q);
while (q--) {
int tp; scanf("%d", &tp);
if (tp == 1) {
int x; scanf("%d", &x);
for (int i = 1; i <= k; ++i) scanf("%d", &inp[i]);
ms(s, 0);
for (int S = 0; S < (1 << k); ++S) {
for (int i = 1; i <= k; ++i) {
s[S] += ((S & (1 << (i - 1))) ? 1ll : -1ll) * inp[i];
}
}
update(1, 1, n, x);
}
if (tp == 2) {
int l, r; scanf("%d%d", &l, &r);
for (int S = 0; S < (1 << k); ++S) retmax[S] = -INF, retmin[S] = INF;
query(1, 1, n, l, r);
LL ans = 0;
for (int i = 1; i < (1 << k); ++i) ans = max(ans, retmax[i] - retmin[i]);
printf("%lld\n", ans);
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
