题意
在 \(k\) 维空间中，处理 \(q\) 个如下两种类型的操作：
- \(1\ i\ b_1\ b_2\ \dots\ b_k\) —— 将第 \(i\) 个点的坐标设为 \((b_1, b_2, \dots, b_k)\)；
- \(2\ l\ r\) —— 查询区间 \([l, r]\) 内任意两点 \(a_i\) 和 \(a_j\) 之间的最大曼哈顿距离（\(l \leq i, j \leq r\)）。
\(1 \leq n,q \leq 2 \times 10^5\)，\(1 \leq k \leq 5\)，\(-10^6 \leq b_{i,j} \leq 10^6\)
题解
观察到 \(k\) 很小，暴力将曼哈顿距离中的绝对值拆开。
定义 \(f[i][x]\) 第 \(i\) 个数状态为 \(x\) 时的和。
状态定义为对于 \(x\) 二进制下的第 \(i\) 位，则其系数取正，否则取负。
容易观察到最终答案就是 \(\max \{f_1+f_{30},f_2+f_{29},......\}\)
开 \(32\) 个线段树即可。
代码
#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
// #define int long long
using namespace std;
const int Maxn=2e5+10;
int n,q,k;
struct status
{int a[32];status() {memset(a,0xcf,sizeof(a));}void operator =(const vector<int> &x){for(int i=0;i<(1<<k);i++){a[i]=0;for(int j=0;j<k;j++){if(i&(1<<j)) a[i]+=x[j];else a[i]-=x[j];}}}
};
status f[4*Maxn];
status operator+(status x,status y)
{status re;for(int i=0;i<(1<<k);i++) re.a[i]=max(x.a[i],y.a[i]);return re;
}
void push_up(int p) {f[p]=f[ls]+f[rs];}
void change(int p,int l,int r,int tar,vector<int>x)
{if(l==r) return f[p]=x,void();if(tar<=mid) change(ls,l,mid,tar,x);else change(rs,mid+1,r,tar,x);push_up(p);
}
status query(int p,int l,int r,int tl,int tr)
{if(tl<=l && tr>=r) return f[p];if(tr<=mid) return query(ls,l,mid,tl,tr);if(tl>mid) return query(rs,mid+1,r,tl,tr);return query(ls,l,mid,tl,tr)+query(rs,mid+1,r,tl,tr);
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){vector<int>v;for(int j=1;j<=k;j++){int x; cin>>x;v.push_back(x);}change(1,1,n,i,v);}cin>>q;while(q--){int opt;cin>>opt;if(opt==1){int p;cin>>p;vector<int>v;for(int i=1;i<=k;i++){int x;cin>>x;v.push_back(x);}change(1,1,n,p,v);}else{int l,r;cin>>l>>r;status re=query(1,1,n,l,r);int ans=0;for(int i=0;i<(1<<k);i++) ans=max(ans,re.a[i]+re.a[(1<<k)-i-1]);cout<<ans<<endl;}}return 0;
}