bzoj 2648: SJY摆棋子【KD-tree】

其实理论上cdq更优

核心是依次取x值、y值的mid作为当前节点，向两边递归建立二叉树，树上维护size：子树大小；mx[0/1]：子树内最大x/y；mn[0/1]：子树内最小x/y；d[0/1]：这个点的x/y；

建树的时候用到nth_element，用处是把第k个数放到k位置，并且把小于k的放在k前，大于k的放在k后（算是快排的一部分）

插入点的时候，像走二叉搜索树一样往下走（不过每走一步key值就要变，xy交替），然后走到空就把新点挂上去

查找的时候比较像退火，通过mnmx找到子树能更新答案的最小值预估，然后决定要不要往下走，并且一路走一路用真实值更新答案；如果左右儿子都能走，就先走估值小的那边

然后出现了一个问题，这个插入有可能把二叉树变成一条链，这个时候要用替罪羊树的思想，设一个阈值，如果左右儿子的size比例超过阈值就把这颗子树拍扁重构

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=500005;

const double alp=0.75;

int n,m,w,tot,rt,ans;

struct qwe

{

	int a[2];

	int& operator [] (int x)

	{

		return a[x];

	}

	bool operator < (const qwe &b) const

	{

		return a[w]<b.a[w];

	}

}a[N];

struct KD

{

	int s,ls,rs,mn[2],mx[2];

	qwe d;

}t[N*5];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void minn(int &x,int y)

{

	x>y?x=y:0;

}

void maxx(int &x,int y)

{

	x<y?x=y:0;

}

void ud(int ro)

{

	if(t[ro].ls)

		for(int i=0;i<=1;i++)

			minn(t[ro].mn[i],t[t[ro].ls].mn[i]),maxx(t[ro].mx[i],t[t[ro].ls].mx[i]);

	if(t[ro].rs)

		for(int i=0;i<=1;i++)

			minn(t[ro].mn[i],t[t[ro].rs].mn[i]),maxx(t[ro].mx[i],t[t[ro].rs].mx[i]);

	t[ro].s=t[t[ro].ls].s+t[t[ro].rs].s+1;

}

int build(int l,int r,int f)

{

	if(l>r)

		return 0;

	w=f;

	int mid=(l+r)>>1,ro=++tot;

	nth_element(a+l,a+mid,a+r+1);

	t[ro].s=1;

	t[ro].d[0]=t[ro].mn[0]=t[ro].mx[0]=a[mid][0];

	t[ro].d[1]=t[ro].mn[1]=t[ro].mx[1]=a[mid][1];

	t[ro].ls=build(l,mid-1,f^1);

	t[ro].rs=build(mid+1,r,f^1);

	ud(ro);

	return ro;

}

void pia(int &ro,int s)

{

	if(t[ro].ls)

		pia(t[ro].ls,s);

	a[s+t[t[ro].ls].s+1]=t[ro].d;

	if(t[ro].rs)

		pia(t[ro].rs,s+t[t[ro].ls].s+1);

}

void ok(int &ro,int f)

{

	if(alp*t[ro].s<max(t[t[ro].ls].s,t[t[ro].rs].s))

		pia(ro,0),ro=build(1,t[ro].s,f);

}

void update(int &ro,int x,int y,int f)

{

	if(!ro)

	{

		ro=++tot;

		t[ro].s=1;

		t[ro].mn[0]=t[ro].mx[0]=t[ro].d[0]=x;

		t[ro].mn[1]=t[ro].mx[1]=t[ro].d[1]=y;

		return;

	}

	if(t[ro].d[f]>=(f==0?x:y))

		update(t[ro].ls,x,y,f^1);

	else

		update(t[ro].rs,x,y,f^1);

	ud(ro);

	ok(ro,f);

}

int dis(int ro,int x,int y)

{

	return max(x-t[ro].mx[0],0)+max(t[ro].mn[0]-x,0)+max(y-t[ro].mx[1],0)+max(t[ro].mn[1]-y,0);

}

void ques(int ro,int x,int y)

{

	ans=min(ans,abs(x-t[ro].d[0])+abs(y-t[ro].d[1]));

	int dl=t[ro].ls?dis(t[ro].ls,x,y):1e9,dr=t[ro].rs?dis(t[ro].rs,x,y):1e9;

	if(dl<dr)

	{

		if(dl<ans)

			ques(t[ro].ls,x,y);

		if(dr<ans)

			ques(t[ro].rs,x,y);

	}

	else

	{

		if(dr<ans)

			ques(t[ro].rs,x,y);

		if(dl<ans)

			ques(t[ro].ls,x,y);

	}

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=n;i++)

		a[i][0]=read(),a[i][1]=read();

	rt=build(1,n,0);

	while(m--)

	{

		int o=read(),x=read(),y=read();

		if(o==1)

			update(rt,x,y,0);

		else

		{

			ans=1e9;

			ques(rt,x,y);

			printf("%d\n",ans);

		}

	}

	return 0;

}

巴特西

bzoj 2648: SJY摆棋子【KD-tree】

最新文章

热门文章