题解 BZOJ 2648 SJY摆棋子

双倍经验2716.
KD-Tree模板题。
注意一下"nth_element()"
参考： http://blog.csdn.net/jiangshibiao/article/details/34144829

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,D,root,x,y;
struct N{
	int d[2];
	int l,r;
	int min[2];
	int max[2];
}a[1000005];
bool cmp(const N&a,const N&b){
	if(a.d[D]!=b.d[D]) return a.d[D]<b.d[D];
	return a.d[D^1]<b.d[D^1];
}
inline void up(int k,int s){
	a[k].min[0]=min(a[k].min[0],a[s].min[0]);
	a[k].min[1]=min(a[k].min[1],a[s].min[1]);
	a[k].max[0]=max(a[k].max[0],a[s].max[0]);
	a[k].max[1]=max(a[k].max[1],a[s].max[1]);
}
int bd(int l,int r,int d){
	D=d;
	int mid=(l+r)>>1;
	nth_element(a+l,a+mid+1,a+r+1,cmp);
	a[mid].min[0]=a[mid].max[0]=a[mid].d[0];
	a[mid].min[1]=a[mid].max[1]=a[mid].d[1];
	if(l!=mid) a[mid].l=bd(l,mid-1,d^1);
	if(r!=mid) a[mid].r=bd(mid+1,r,d^1);
	if(a[mid].l) up(mid,a[mid].l);
	if(a[mid].r) up(mid,a[mid].r);
	return mid;
}
const int inf=0x7fffffff;
int ans;
int getdis(int k){
	int ret=0;
	if(x<a[k].min[0]) ret+=a[k].min[0]-x;
	if(x>a[k].max[0]) ret+=x-a[k].max[0];
	if(y<a[k].min[1]) ret+=a[k].min[1]-y;
	if(y>a[k].max[1]) ret+=y-a[k].max[1];
	return ret;
}
void ask(int k){
	int d0=abs(a[k].d[0]-x)+abs(a[k].d[1]-y);
	if(d0<ans) ans=d0;
	int d1=(a[k].l)?getdis(a[k].l):inf;
	int d2=(a[k].r)?getdis(a[k].r):inf;
	if(d1<d2){
		if(d1<ans) ask(a[k].l);
		if(d2<ans) ask(a[k].r);
	}else{
		if(d2<ans) ask(a[k].r);
		if(d1<ans) ask(a[k].l);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].d[0],&a[i].d[1]);
	}
	root=bd(1,n,0);
	for(int i=0,t;i<m;i++){
		scanf("%d%d%d",&t,&x,&y);
		if(t==1){
			n++;
			a[n].min[0]=a[n].max[0]=a[n].d[0]=x;
			a[n].min[1]=a[n].max[1]=a[n].d[1]=y;
			int p=root,D=0;
			while(1){
				up(p,n);
				if(a[n].d[D]<a[p].d[D]){
					if(!a[p].l) {
						a[p].l=n;
						break;
					}else{
						p=a[p].l;
					}
				}else{
					if(!a[p].r) {
						a[p].r=n;
						break;
					}else{
						p=a[p].r;
					}
				}
				D^=1;
			}
		}else{
			ans=inf;
			ask(root);
			printf("%d\n",ans);
		}
	}
	return 0;
}