首页 > 代码库 > BZOJ 2735: 世博会 主席树+切比雪夫距离转曼哈顿距离

BZOJ 2735: 世博会 主席树+切比雪夫距离转曼哈顿距离

2024-10-17 10:17:02   213人阅读

2735: 世博会

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 124  Solved: 51
[Submit][Status][Discuss]

Description

四年一度的世博会又要举办了，Q国很荣幸成为了这次世博会的主办方。Q国主席QQ从全国各地收集了N件物品排成
一排，作为Q国馆的展出物。对于相邻摆放的一些物品，如果过于相似会让人觉得无聊，如果差别过大又会让人觉
得突兀。为了让人们对这次世博会的展出满意，QQ需要知道一些相邻物品的“差异度”。为了方便表示，QQ给每个
物品都定义了两个属性值A、B，两件物品之间的“绝对差异值”定义为它们对应属性的差的绝对值较大的一个。对
于一些物品的“差异度”，类似求方差的方法，QQ总会首先设想一个理想的“平均物品”，它的两个属性可以为任
意实数，且它与这些物品中的每个物品的“绝对差异值”之和最小。而这些物品的“差异度”就定义为这个最小的
和。QQ每次会询问：从第Li个到第Ri个物品的“差异度”是多少。现在，这个任务交给了神犇你。

Input

第一行两个整数N和Q，表示物品数和QQ的询问数。第二行N个整数A1到An，表示每个物品的A属性。第三行N个整数B
1到Bn，表示每个物品的B属性。之后Q行每行两个整数Li Ri，表示QQ的询问。
1<=N<=100000, 1<=Q<=100000, |Ai|,|Bi|<=1000000000,1<=Li<=Ri<=N

Output

共Q行，每行输出一个数，表示该次询问的物品的差异度，结果保留到小数点后两位。

Sample Input

4 2
1 6 -3 2
2 7 -1 3
1 4
2 3

Sample Output

10.00
9.00
样例说明
对于第一个询问，平均物品的两个属性可以是1和2差异度为max(0,0)+max(5,5)+max(4,3)+max(1,1)=10对于第二个
询问，平均物品的两个属性可以是6和7差异度为max(0,0)+max(9,8)=9
 

Solution

题意：每次询问要你给出$(A_0,B_0)$，最小化$\sum_{i=L}^{R} max{|A_i-A_0|,|B_i-B_0|} $。
 
先来点干货：

  • 切比雪夫距离：每一维差绝对值的最大值  $max\{|x_i-x_j|,|y_i-y_j|\}$

  • 曼哈顿距离：每一维差绝对值之和 $|x_i-x_j|+|y_i-y_j|$

  • 二维切比雪夫距离转曼哈顿距离：把坐标系旋转一下，然后再拉伸下。$(x,y)->(\frac{1}{2}(x-y),\frac{1}{2}(x+y))$

想法：将(A,B)当成二维坐标。然后再转换为(A-B,A+B)。问题变成最小化$\sum_{i=L}^{R} {|A_i-A_0|+|B_i-B_0|} $。每一维是独立的，并且每一维选中位数是最优的之一。所以用主席树维护一下查第K大，前\后缀和。

Code $O(n \log n)$ 

#include < cstdio >#include < algorithm >#define gec     getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG   fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__)typedef long long ll;template < typename T >inline void read(T &x){	x=0;bool f=0; char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int MAXN(100010);int n,q,A[MAXN],B[MAXN],X[MAXN],Y[MAXN];struct AXLE{	int a[MAXN],up;	void ins(int x){a[++up]=x;}	void build()	{		std::sort(a+1,a+1+up);		int _up=1;		for(int i=2;i<=up;i++)if(a[i]!=a[i-1])a[++_up]=a[i];		up=_up;	}	int Find(int x)	{		int l=1,r=up,mid,id=1;		while(l<=r)if(a[mid=(l+r)>>1]<=x)l=mid+1,id=mid;else r=mid-1;		return id;	}}axle;namespace ChairMan_Tree{	const int MAX_L(2000010);	struct CMT	{		int nx[MAX_L][2],Siz[MAX_L]; 	 ll Sum[MAX_L];		int root[MAXN],stot,Val[MAXN],N;				void update(int k)		{Sum[k]=Sum[nx[k][0]]+Sum[nx[k][1]];		 Siz[k]=Siz[nx[k][0]]+Siz[nx[k][1]];}				void modfiy(int&k,int k2,int L,int R,int x)//val[x]++;		{				if(!k)k=++stot,Sum[k]=Sum[k2],Siz[k]=Siz[k2];			if(L==R){Sum[k]+=Val[x];Siz[k]++; return ;}			int MID=(L+R)>>1;			if(x<=MID)modfiy(nx[k][0],nx[k2][0],L,MID,x),nx[k][1]=nx[k2][1];			else 	modfiy(nx[k][1],nx[k2][1],MID+1,R,x),nx[k][0]=nx[k2][0];			update(k);		}				ll Que(int k1,int k2,int Rank)//查询区间第K大以及前\后缀和		{			int L=1,R=N,MID,Siz_L=0,Siz_R=0;			ll Sum_L=0,Sum_R=0;			while(L!=R)			{				MID=(L+R)>>1;//				fprintf(stderr,"%d %d %d\n",L,R,Rank);//				fprintf(stderr,"%d\n",Siz[nx[k1][0]]-Siz[nx[k2][0]]);				if(Siz[nx[k1][0]]-Siz[nx[k2][0]]<Rank)				Siz_L+=Siz[nx[k1][0]]-Siz[nx[k2][0]],Sum_L+=Sum[nx[k1][0]]-Sum[nx[k2][0]],//				fprintf(stderr,"%d %d %lld\n",L,MID,Sum[nx[k1][0]]-Sum[nx[k2][0]]),				L=MID+1,Rank-=Siz[nx[k1][0]]-Siz[nx[k2][0]],k1=nx[k1][1],k2=nx[k2][1];				else				Siz_R+=Siz[nx[k1][1]]-Siz[nx[k2][1]],Sum_R+=Sum[nx[k1][1]]-Sum[nx[k2][1]],				R=MID,k1=nx[k1][0],k2=nx[k2][0];			}//			fprintf(stderr,"%lld %d %lld %d %d %d\n",Sum_L,Siz_L,Sum_R,Siz_R,L,Val[L]);			return (ll)Siz_L*Val[L]-Sum_L+Sum_R-(ll)Siz_R*Val[L];		}			}A_Tree,B_Tree;	}using namespace ChairMan_Tree;void Pretreat(){	for(int i=1;i<=n;i++)axle.ins(A[i]); axle.build();	for(int i=1;i<=n;i++)A[i]=axle.Find(A[i]);	A_Tree.N=axle.up; for(int i=1;i<=A_Tree.N;i++)A_Tree.Val[i]=axle.a[i];	for(int i=1;i<=n;i++)A_Tree.modfiy(A_Tree.root[i],A_Tree.root[i-1],1,A_Tree.N,A[i]);	axle.up=0;	for(int i=1;i<=n;i++)axle.ins(B[i]); axle.build();	for(int i=1;i<=n;i++)B[i]=axle.Find(B[i]);	B_Tree.N=axle.up; for(int i=1;i<=B_Tree.N;i++)B_Tree.Val[i]=axle.a[i];	for(int i=1;i<=n;i++)B_Tree.modfiy(B_Tree.root[i],B_Tree.root[i-1],1,B_Tree.N,B[i]);}int main(){#ifndef ONLINE_JUDGE	FILE("C");#endif 	read(n);read(q);	for(int i=1;i<=n;i++)read(X[i]);	for(int i=1;i<=n;i++)read(Y[i]);	for(int i=1;i<=n;i++)A[i]=X[i]-Y[i],B[i]=X[i]+Y[i];	Pretreat();	for(int i=1,L,R;i<=q;i++)	{		read(L);read(R);		ll Ans_A=A_Tree.Que(A_Tree.root[R],A_Tree.root[L-1],(R-L+2)>>1);		ll Ans_B=B_Tree.Que(B_Tree.root[R],B_Tree.root[L-1],(R-L+2)>>1);		printf("%.2lf\n",(Ans_A+Ans_B)*0.5);	}	return 0;}

BZOJ 2735: 世博会 主席树+切比雪夫距离转曼哈顿距离


联系
我们