题解 CF1093G 【Multidimensional Queries】
ouuan
2018-12-17 12:00:31
> 为了便于扩展到高维,本文中点的坐标统一用 $(x_1,x_2,\cdots,x_k)$ 表示,即使二维也一样。
$\begin{aligned}&\text{两个二维点之间的曼哈顿距离}\\=&|x_1-y_1|+|x_2-y_2|\\=&\max(x_1-y_1,y_1-x_1)+\max(x_2-y_2,y_2-x_2)\\=&\max(x_1-y_1+x_2-y_2,x_1-y_1+y_2-x_2,y_1-x_1+x_2-y_2,y_1-x_1+y_2-x_2)\end{aligned}$
用 $s[x][0]$ 表示 $-x_1-x_2$,$s[x][1]$ 表示 $-x_1+x_2$,$s[x][2]$ 表示 $x_1-x_2$,$s[x][3]$ 表示 $x_1+x_2$,那么 $\text{两个二维点之间的曼哈顿距离}=\max\{s[x][j]-s[y][j]\}(j\in[0,3])$ 。
转换成这样之后,二维平面上一些点之间的最大曼哈顿距离就可以求了:$\max\{\max\{s[a_i][j]\}-\min\{s[a_i][j]\}\}$
上面这个公式的意思是,对于每个 $j$ 把 $s[a_{1..n}][j]$ 求出来,并取最大值和最小值相减,把不同的 $j$ 的“最大值和最小值相减”取 $\max$ 。
至于高维,二进制枚举 $x_i$ 的正负,也就是说 $s[x][j]=\sum_{i=1}^kx_i\times(j\text{ and } 2^{i-1}?1:-1)$,然后按一样的做法就可以了。
如果到这里为止你看懂了,你就可以 AC [P1648 看守](https://www.luogu.org/problemnew/show/P1648) 了。
至于本题,需要支持区间查询、单点修改,套上任何一种支持修改的 RMQ(比如线段树)即可。
但是套有不同的套法,直接放在一棵线段树里,每个节点存 $2^k$ 个最大/最小值,修改/询问时就只用在线段树上查找一次;如果拆成 $32$ 棵线段树,常数就会非常大。
一棵线段树的 $1.1s$ 解法:
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
inline int read()
{
char c;int out=0,f=1;
for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());if (c=='-'){f=-1;c=getchar();}
for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}return out*f;
}
void write(int x)
{
if (x<0){putchar('-');write(-x);return;}
if (x>9){write(x/10);}putchar(x%10+'0');
}
#define now t[cur]
#define ls t[cur<<1]
#define rs t[cur<<1|1]
const int N=200010;
int n,k,q,a[N][5];
struct Val
{
int maxx[32],minn[32];
Val()
{
int i;
for (i=0;i<(1<<k);++i)
{
maxx[i]=-INF;
minn[i]=INF;
}
}
};
struct Node
{
int left,right;
Val val;
} t[N<<2];
void build(int cur,int l,int r);
void mnode(int cur);
void modify(int cur,int p);
Val query(int cur,int l,int r);
Val merge(Val x,Val y);
int main()
{
int i,j,pos,l,r,ans;
Val v;
n=read();
k=read();
for (i=1;i<=n;++i)
{
for (j=0;j<k;++j)
{
a[i][j]=read();
}
}
build(1,1,n+1);
q=read();
while (q--)
{
if (read()==1)
{
pos=read();
for (i=0;i<k;++i)
{
a[pos][i]=read();
}
modify(1,pos);
}
else
{
ans=0;
l=read();
r=read();
v=query(1,l,r+1);
for (i=0;i<(1<<k);++i)
{
ans=max(ans,v.maxx[i]-v.minn[i]);
}
write(ans);
putchar('\n');
}
}
return 0;
}
void mnode(int cur)
{
int i,j;
for (i=0;i<(1<<k);++i)
{
now.val.maxx[i]=0;
for (j=0;j<k;++j)
{
now.val.maxx[i]+=((i&(1<<j))?1:-1)*a[now.left][j];
}
now.val.minn[i]=now.val.maxx[i];
}
}
void build(int cur,int l,int r)
{
now.left=l;
now.right=r;
if (l==r-1)
{
mnode(cur);
}
else
{
build(cur<<1,l,(l+r)>>1);
build(cur<<1|1,(l+r)>>1,r);
now.val=merge(ls.val,rs.val);
}
}
void modify(int cur,int p)
{
if (now.left==p&&now.right==p+1)
{
mnode(cur);
}
else
{
if (p<ls.right)
{
modify(cur<<1,p);
}
else
{
modify(cur<<1|1,p);
}
now.val=merge(ls.val,rs.val);
}
}
Val query(int cur,int l,int r)
{
if (l>=now.right||r<=now.left)
{
return Val();
}
if (l<=now.left&&r>=now.right)
{
return now.val;
}
else
{
return merge(query(cur<<1,l,r),query(cur<<1|1,l,r));
}
}
Val merge(Val x,Val y)
{
Val out;
int i;
for (i=0;i<(1<<k);++i)
{
out.minn[i]=min(x.minn[i],y.minn[i]);
out.maxx[i]=max(x.maxx[i],y.maxx[i]);
}
return out;
}
```
拆成 $32$ 棵线段树的 $4.2s$ 解法:
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
inline int read()
{
char c;int out=0,f=1;
for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());if (c=='-'){f=-1;c=getchar();}
for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}return out*f;
}
void write(int x)
{
if (x<0){putchar('-');write(-x);return;}
if (x>9){write(x/10);}putchar(x%10+'0');
}
#define now t[cur]
#define ls t[cur<<1]
#define rs t[cur<<1|1]
const int N=200010;
struct Node
{
int left,right,maxx,minn;
};
int n,k,q,a[N][5];
struct segTree
{
int b[N];
Node t[N<<2];
void build(int cur,int l,int r)
{
now.left=l;
now.right=r;
if (l==r-1)
{
now.maxx=now.minn=b[l];
}
else
{
build(cur<<1,l,(l+r)>>1);
build(cur<<1|1,(l+r)>>1,r);
pushup(cur);
}
}
void modify(int cur,int p,int x)
{
if (p==now.left&&p==now.right-1)
{
now.minn=now.maxx=x;
}
else
{
if (p<ls.right)
{
modify(cur<<1,p,x);
}
else
{
modify(cur<<1|1,p,x);
}
pushup(cur);
}
}
int qmax(int cur,int l,int r)
{
if (l>=now.right||r<=now.left)
{
return -INF;
}
if (l<=now.left&&r>=now.right)
{
return now.maxx;
}
else
{
return max(qmax(cur<<1,l,r),qmax(cur<<1|1,l,r));
}
}
int qmin(int cur,int l,int r)
{
if (l>=now.right||r<=now.left)
{
return INF;
}
if (l<=now.left&&r>=now.right)
{
return now.minn;
}
else
{
return min(qmin(cur<<1,l,r),qmin(cur<<1|1,l,r));
}
}
void pushup(int cur)
{
now.minn=min(ls.minn,rs.minn);
now.maxx=max(ls.maxx,rs.maxx);
}
} s[32];
int main()
{
int i,j,l,r,ans;
n=read();
k=read();
for (i=1;i<=n;++i)
{
for (j=0;j<k;++j)
{
a[i][j]=read();
}
for (j=0;j<(1<<k);++j)
{
for (l=0;l<k;++l)
{
if (j&(1<<l))
{
s[j].b[i]+=a[i][l];
}
else
{
s[j].b[i]-=a[i][l];
}
}
}
}
for (i=0;i<(1<<k);++i)
{
s[i].build(1,1,n+1);
}
q=read();
while (q--)
{
if (read()==1)
{
i=read();
for (j=0;j<k;++j)
{
a[i][j]=read();
}
for (j=0;j<(1<<k);++j)
{
s[j].b[i]=0;
for (l=0;l<k;++l)
{
if (j&(1<<l))
{
s[j].b[i]+=a[i][l];
}
else
{
s[j].b[i]-=a[i][l];
}
}
s[j].modify(1,i,s[j].b[i]);
}
}
else
{
l=read();
r=read()+1;
ans=0;
for (i=0;i<(1<<k);++i)
{
ans=max(ans,s[i].qmax(1,l,r)-s[i].qmin(1,l,r));
}
write(ans);
putchar('\n');
}
}
return 0;
}
```