[bzoj2648] SJY 자갈kd-tree

kd-tree를 배웠는데 어떤 평면 문제에 있어서 독특한 장점을 가지고 있는 것 같아요.
kd-tree는 항상 n개의 점으로 평면을 n+1블록으로 구분하고 구분하는 방식이다. 현재 층에 대해 x좌표를 키워드로 하여 x좌표가 중간에 있는 점p를 찾은 다음에 이 구간을 두 블록으로 나누면 한 블록의 x좌표는 p보다 작고 다른 블록의 x좌표는 p보다 크다.그리고 각각 두 덩어리로 돌아가지만, 그 두 덩어리의 키워드는 y 좌표이다.그리고 x좌표 한 층, y좌표 한 층을 차례로 내려가면 직관적이다.(그리고 현재 층의 상황에 따라 x좌표인지 y좌표를 키워드로 하는지 결정한다. 여기서 생략한다.)
점을 삽입하면 이 점이 있는 블록을 찾아서 아버지 노드의 키워드가 가로 좌표인지 세로 좌표인지에 따라 있는 블록을 두 조각으로 나눈다.그래도 최악은 O(N)급이야.(희생양 나무의 폭력으로 사상을 재구성할 수 있을까? 하지만 나는 희생양 나무도 쓸 줄 모르는데 어떻게 쓸 수 있겠는가)
점 p를 조회합니다.마찬가지로 그것이 있는 블록을 찾은 다음에 먼저 ans=dist (p, 이 블록에 대응하는 점) 를 찾습니다.그리고 거슬러 올라갈 때마다 한 점에서 그것이 있는 블록을 두 개로 나누었는데 그 중 하나는 p를 포함했다. 우리는 먼저 p를 원심으로 하고 ans를 반경으로 원(유클리드 거리는 원, 맨해튼 거리는 정사각형)을 그려서 다른 것과 교차할지 확인하고 교차하면 다른 것을 조회한다.때때로 두 개의 하위 노드가 모두 조회되기 때문에 O(logN)가 아니라 O(N^0.5)일 수 있습니까?
그리고 이 문제는 누드문제 매운 2333~\(≥≤)/~
AC 코드는 다음과 같습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1000005
#define inf 1000000000
using namespace std;

int n,m,dim,rt,ans;
int read(){
	int x=0; char ch=getchar();
	while (ch<'0' || ch>'9') ch=getchar();
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return x;
}
struct node{ int p[2],x[2],y[2]; }a[N];
bool cmp(node x,node y){ return x.p[dim]<y.p[dim]; }
struct kd_tree{
	int c[N][2]; node s[N],q;
	void maintain(int k){
		int l=c[k][0],r=c[k][1],i;
		for (i=0; i<2; i++){
			if (l){ s[k].x[i]=min(s[k].x[i],s[l].x[i]); s[k].y[i]=max(s[k].y[i],s[l].y[i]); }
			if (r){ s[k].x[i]=min(s[k].x[i],s[r].x[i]); s[k].y[i]=max(s[k].y[i],s[r].y[i]); }
		}
	}
	void add(int k,node t){
		int i; for (i=0; i<2; i++) s[k].x[i]=s[k].y[i]=s[k].p[i]=t.p[i];
	}
	int dist(node t,int k){
		int tmp=0,i;
		for (i=0; i<2; i++) tmp+=max(0,s[k].x[i]-t.p[i]);
		for (i=0; i<2; i++) tmp+=max(0,t.p[i]-s[k].y[i]);
		return tmp;
	}
	void build(int &k,int l,int r,int now){
		k=(l+r)>>1; dim=now;
		nth_element(a+l,a+k,a+r+1,cmp);
		add(k,a[k]);
		if (l<k) build(c[k][0],l,k-1,now^1);
		if (k<r) build(c[k][1],k+1,r,now^1);
		maintain(k);
	}
	void ins(int k,int now){
		if (q.p[now]<s[k].p[now])
			if (c[k][0]) ins(c[k][0],now^1); else{
				c[k][0]=++n; add(n,q);
			}
		else
			if (c[k][1]) ins(c[k][1],now^1); else{
				c[k][1]=++n; add(n,q);
			}
		maintain(k);
	}
	void qry(int k){
		ans=min(ans,abs(s[k].p[0]-q.p[0])+abs(s[k].p[1]-q.p[1]));
		int dl=(c[k][0])?dist(q,c[k][0]):inf,dr=(c[k][1])?dist(q,c[k][1]):inf;
		if (dl<dr){
			if (dl<ans) qry(c[k][0]); if (dr<ans) qry(c[k][1]);
		} else{
			if (dr<ans) qry(c[k][1]); if (dl<ans) qry(c[k][0]);
		}
	}
}kd;
int main(){
	n=read(); m=read(); int i;
	for (i=1; i<=n; i++) scanf("%d%d",&a[i].p[0],&a[i].p[1]);
	kd.build(rt,1,n,0);
	while (m--){
		int k=read(); kd.q.p[0]=read(); kd.q.p[1]=read();
		if (k==1) kd.ins(rt,0); else{
			ans=inf; kd.qry(rt); printf("%d
",ans);
		}
	}
	return 0;
}

by lych
2016.3.5