题解 CF1093G 【Multidimensional Queries】
XG_Zepto
2018-12-18 20:13:55
首发于 [个人博客](https://zepto.page/post/codeforces-1093g)。
### 思路
$i,j$ 之间的曼哈顿距离被定义为 $\sum |a_{i,k}-a_{j,k}|$。我们可以把式子拆开，每一维上 $a_i$ 和 $a_j$ 取值的正负性一定是相反的。
考虑到 $k$ 比较小，我们可以枚举每个点的第 $i$ 维在距离计算公式中的正负性。
具体地，我们用集合 $S$ 表示一个点每个维度的正负性。用线段树维护区间内每种可能集合 $S$ 的最大值。也就是说，我们分别计算每个点对不同的集合 $S$ 的贡献。合法答案是所有互补集合对贡献和的最大值。
### 代码
```cpp
#include <bits/stdc++.h>
#define ll long long
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 800010
using namespace std;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') flag=-1,ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
struct Seg{
int t[maxn];
inline void update(int l,int r,int x,int v,int p){
if (l==r) {t[p]=v;return;}
int mid=((l+r)>>1);
if (mid>=x) update(l,mid,x,v,ls);
else update(mid+1,r,x,v,rs);
t[p]=max(t[ls],t[rs]);
}
inline int query(int l,int r,int L,int R,int p){
if (L<=l&&r<=R) return t[p];
int mid=((l+r)>>1);
if (R<=mid) return query(l,mid,L,R,ls);
if (L>=mid+1) return query(mid+1,r,L,R,rs);
return max(query(l,mid,L,R,ls),query(mid+1,r,L,R,rs));
}
}mk[32];
int n,k,m,a[6],b[32];
inline void update(int pos){
for (int j=1;j<=k;++j)
a[j]=read();
for (int S=0;S<1<<k;++S){
int sum=0;
for (int j=1;j<=k;++j)
if ((S>>(j-1))&1) sum-=a[j];
else sum+=a[j];
mk[S].update(1,n,pos,sum,1);
}
}
inline void query(int l,int r){
int res=-INT_MAX;
for (int S=0;S<1<<k;++S)
b[S]=mk[S].query(1,n,l,r,1);
for (int S=0;S<1<<k;++S)
res=max(res,b[S]+b[((1<<k)-1)-S]);
printf("%d\n",res);
}
int main(){
n=read(),k=read();
for (int S=0;S<1<<k;++S)
memset(mk[S].t,0x3f,sizeof(mk[S].t));
for (int i=1;i<=n;++i) update(i);
m=read();
for (int i=1,op,pos,l,r;i<=m;++i){
op=read();
if (op==1) pos=read(),update(pos);
if (op==2) l=read(),r=read(),query(l,r);
}
}
```