BZOJ 2648 SJY摆棋子

题目大意

给你一个二维平面，其上有一些点，每次询问距离一个坐标距离最近的点或者插入一个点。

这题下面的HINT栏目中写的是"KDTree可以过"......

时间复杂度似乎是不对的（玄学剪枝），但是因为有HINT就那样吧qwq

不用重构，每次暴力插入点，查询即可。查询有点复杂：首先判断KDT上的该点，之后如果该点的儿子所代表的矩形和该点的距离比答案近的话就递归进行查询。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int ri()
{
	int ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
#define INF 0x3f3f3f3f
int n,m,md,ans,rt;
struct point
{
	int v[2],mn[2],mx[2],ls,rs;
	point(){}
	void init(){ls=rs=0,mn[0]=mx[0]=v[0],mn[1]=mx[1]=v[1];}
	point(int x,int y){ls=rs=0,mn[0]=mx[0]=v[0]=x,mn[1]=mx[1]=v[1]=y;}
	bool operator <(const point &tg)const{return v[md]==tg.v[md]?v[md^1]<tg.v[md^1]:v[md]<tg.v[md];}
}p[1000010];
inline void pushup(int pos,int pre)
{
	p[pos].mn[0]=min(p[pos].mn[0],p[pre].mn[0]);
	p[pos].mn[1]=min(p[pos].mn[1],p[pre].mn[1]);
	p[pos].mx[0]=max(p[pos].mx[0],p[pre].mx[0]);
	p[pos].mx[1]=max(p[pos].mx[1],p[pre].mx[1]);
}
int build(int now,int l,int r)
{
	if(l>r) return 0;
	int mid=(l+r)>>1;
	md=now,nth_element(p+l,p+mid,p+r+1);
	p[mid].ls=build(now^1,l,mid-1),pushup(mid,p[mid].ls);
	p[mid].rs=build(now^1,mid+1,r),pushup(mid,p[mid].rs);
	return mid;
}
void insert(int &pos,int now,int x,int y)
{
	if(!pos) {p[pos=++n]=point(x,y);return;}
	if(!now)
	{
		if(x<=p[pos].v[now]) insert(p[pos].ls,now^1,x,y),pushup(pos,p[pos].ls);
		else				 insert(p[pos].rs,now^1,x,y),pushup(pos,p[pos].rs);
	}
	else
	{
		if(y<=p[pos].v[now]) insert(p[pos].ls,now^1,x,y),pushup(pos,p[pos].ls);
		else				 insert(p[pos].rs,now^1,x,y),pushup(pos,p[pos].rs);
	}
}
inline int getdis(int tg,int x,int y)
{
	int ret=0;
	if(x < p[tg].mn[0]) ret+=p[tg].mn[0]-x;
	if(x > p[tg].mx[0]) ret+=x-p[tg].mx[0];
	if(y < p[tg].mn[1]) ret+=p[tg].mn[1]-y;
	if(y > p[tg].mx[1]) ret+=y-p[tg].mx[1];
	return ret;
}
inline void query(int pos,int x,int y)
{
	ans=min(ans,abs(x-p[pos].v[0])+abs(y-p[pos].v[1]));
	int dl=p[pos].ls?getdis(p[pos].ls,x,y):INF,dr=p[pos].rs?getdis(p[pos].rs,x,y):INF;
	if(dl<dr)
	{
		if(dl<ans) query(p[pos].ls,x,y);
		if(dr<ans) query(p[pos].rs,x,y);
	}
	else
	{
		if(dr<ans) query(p[pos].rs,x,y);
		if(dl<ans) query(p[pos].ls,x,y);
	}
}
int main()
{
	p[0].mx[0]=p[0].mx[1]=-INF,p[0].mn[0]=p[0].mn[1]=INF;
	n=ri(),m=ri();
	for(int i=1;i<=n;++i) p[i].v[0]=ri(),p[i].v[1]=ri(),p[i].init();
	rt=build(0,1,n);
	int tx,ty;
	while(m--)
	{
		md=ri(),tx=ri(),ty=ri();
		switch(md)
		{
			case 1:insert(rt,0,tx,ty);break;
			case 2:ans=0x7fffffff;query(rt,tx,ty);printf("%d\n",ans);break;
		}
	}
	return 0;
}