【Codeforces 1093G】Multidimensional Queries / 题解

Description

给定 $n$ 个 $k$ 维整点 $\{ a_i \}$,支持单点坐标修改,求区间 $[l,r]$ 内点对的最长曼哈顿距离。

Idea

$i,j$ 之间的曼哈顿距离被定义为 $\sum |a_{i,k}-a_{j,k}|$。我们可以把式子拆开,每一维上 $a_i$ 和 $a_j$ 取值的正负性一定是相反的。

考虑到 $k$ 比较小,我们可以枚举每个点的第 $i$ 维在距离计算公式中的正负性。

具体地,我们用集合 $S$ 表示一个点每个维度的正负性。用线段树维护区间内每种可能集合 $S$ 的最大值。也就是说,我们分别计算每个点对不同的集合 $S$ 的贡献。合法答案是所有互补集合对贡献和的最大值。

Code

#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);
	}
}
Show Comments