题解 CF1093G 【Multidimensional Queries】

ouuan

2018-12-17 12:00:31

Solution

> 为了便于扩展到高维,本文中点的坐标统一用 $(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; } ```