spy(主席树)

题目为某次雅礼集训...

对于\(\max\{a-A_i,\ A_i-a,\ b-B_i,\ B_i-b\}\)，令\(x_1=\frac{a+b}{2},\ y_1=\frac{a-b}{2},\ x_2=\frac{A_i+B_i}{2},\ y_2=\frac{A_i-B_i}{2}\)，那么\(\max\)就可以写成\(\max\{x_1-x_2+y_1-y_2,\ -(x_1-x_2)-(y_1-y_2),\ x_1-x_2-(y_1-y_2),\ -(x_1-x_2)+y_1-y_2\}\)。

注意到两项的正负都取到了，我们就可以写成\(\pm(x_1-x_2)\pm(y_1-y_2)=|x_1-x_2|+|y_1-y_2|\)。两项是独立的了，我们可以分别算。

\(x_2,y_2\)是确定的，现在要确定一个\(x_1,y_1\)，使得\(\sum|x_1-x_{2,i}|+\sum|y_1-y_{2,i}|\)最小（确定出\(x_1,y_1\)我们显然可以确定出\(a,b\)）。

这个问题...考虑一个问题：数轴上有些点，选择一个位置使得它到所有点的距离和最小，就是\(\min\{\sum|p-x_i|\}\)，我们取中位数就可以了。

对于\(\sum|x_1-x_{2,i}|\)，同样取\(x_2\)的中位数就可以了。区间中位数可以用主席树求。

懒得离散化了...

//6026ms	137.211MiB

#include <cmath>

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 500000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1e5+5;

int A[N],B[N],root1[N],root2[N];

char IN[MAXIN],*SS=IN,*TT=IN;

struct Segment_Tree

{

	#define ls son[x][0]

	#define rs son[x][1]

	#define S N*35

	int tot,sz[S],son[S][2];

	LL ans,sum[S];

	#undef S

	void Insert(int &x,int y,int l,int r,int p)

	{

		sz[x=++tot]=sz[y]+1, sum[x]=sum[y]+p;

		if(l==r) return;

		int m=(LL)l+r>>1;//LL!

		p<=m?(rs=son[y][1],Insert(ls,son[y][0],l,m,p)):(ls=son[y][0],Insert(rs,son[y][1],m+1,r,p));

	}

	int Query(int x,int y,int l,int r,int k)//x-y

	{

		if(l==r) return l;

		int m=(LL)l+r>>1,mid,t=sz[ls]-sz[son[y][0]];

		if(t>=k)

			mid=Query(ls,son[y][0],l,m,k), ans+=sum[rs]-sum[son[y][1]]-1ll*mid*(sz[rs]-sz[son[y][1]]);

		else

			mid=Query(rs,son[y][1],m+1,r,k-t), ans+=1ll*mid*(sz[ls]-sz[son[y][0]])-(sum[ls]-sum[son[y][0]]);

		return mid;

	}

}T1,T2;

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());

	for(;isdigit(c);now=now*10+c-48,c=gc());

	return now*f;

}

int main()

{

//	freopen("spy.in","r",stdin);

//	freopen("spy.out","w",stdout);

	#define S1 L1,R1

	#define S2 L2,R2

	int n=read(),q=read(),mnA=1e9,mxA=-1e9,mnB=1e9,mxB=-1e9;

	for(int i=1; i<=n; ++i) A[i]=read(),mnA=std::min(mnA,A[i]),mxA=std::max(mxA,A[i]);

	for(int i=1; i<=n; ++i) B[i]=read(),mnB=std::min(mnB,B[i]),mxB=std::max(mxB,B[i]);

	int L1=mnA+mnB,R1=mxA+mxB,L2=mnA-mxB,R2=mxA-mnB;

	for(int i=1; i<=n; ++i) T1.Insert(root1[i],root1[i-1],S1,A[i]+B[i]), T2.Insert(root2[i],root2[i-1],S2,A[i]-B[i]);

	for(; q--; )

	{

		int l=read(),r=read(),p=r-l+2>>1;

		T1.ans=0, T2.ans=0, T1.Query(root1[r],root1[l-1],S1,p), T2.Query(root2[r],root2[l-1],S2,p);

		printf("%.2lf\n",(T1.ans+T2.ans)*0.5);

	}

	return 0;

}

巴特西

spy(主席树)

最新文章

热门文章