bzoj2628 kdtree 模板

#include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; const int N=1000005; int ans,n,m,t,x,y; int rt,D; struct aaa { int d[2]; int mx[2],mi[2]; int l,r; }a[N]; bool cmp(aaa a,aaa b) { return a.d[D]<b.d[D]||(a.d[D]==b.d[D]&&a.d[D^1]<b.d[D^1]); } void up(int i,int k) { a[i].mi[0]=min(a[i].mi[0],a[k].mi[0]); a[i].mx[0]=max(a[i].mx[0],a[k].mx[0]); a[i].mi[1]=min(a[i].mi[1],a[k].mi[1]); a[i].mx[1]=max(a[i].mx[1],a[k].mx[1]); } int build(int l,int r,int d) { D=d; int mid=(l+r)>>1; nth_element(a+l,a+mid,a+r+1,cmp);//stl的运用 a[mid].mi[0]=a[mid].mx[0]=a[mid].d[0]; a[mid].mi[1]=a[mid].mx[1]=a[mid].d[1]; if (mid>l) a[mid].l=build(l,mid-1,d^1),up(mid,a[mid].l);else a[mid].l=0; if (mid<r) a[mid].r=build(mid+1,r,d^1),up(mid,a[mid].r);else a[mid].r=0; return mid; } void insert(int k)//类似于splay的插入 { int u=rt,d=0; while (true) { up(u,k); if (a[u].d[d]>a[k].d[d]) {if (!a[u].l){a[u].l=k;return;}u=a[u].l;} else {if (!a[u].r){a[u].r=k;return;}u=a[u].r;} d=d^1; } } int f(int u) { if (u==0) return 1e9; int res=0; if (a[u].mi[0]>x) res+=a[u].mi[0]-x; if (a[u].mx[0]<x) res+=x-a[u].mx[0]; if (a[u].mi[1]>y) res+=a[u].mi[1]-y; if (a[u].mx[1]<y) res+=y-a[u].mx[1]; return res; } void query(int u) { #define dis(u) abs(a[u].d[0]-x)+abs(a[u].d[1]-y) ans=min(ans,dis(u)); int dl=f(a[u].l),dr=f(a[u].r);//估价函数，注意左右孩子不存在的情况 if (dl<dr){if (dl<ans) query(a[u].l);if (dr<ans) query(a[u].r);} else {if (dr<ans) query(a[u].r);if (dl<ans) query(a[u].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]); rt=build(1,n,0); for (int i=1;i<=m;i++) { scanf("%d%d%d",&t,&x,&y); if (t==1) { n++; a[n].mi[0]=a[n].mx[0]=a[n].d[0]=x; a[n].mi[1]=a[n].mx[1]=a[n].d[1]=y; insert(n); } else { ans=1e9; query(rt); printf("%d\n",ans); } } return 0; }