kdtree可以过

鸣谢 孙嘉裕

  1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<cstring>  5 #include<queue>  6 using namespace std;  7 const int INF=1e9;  8 const int mxn=500010;  9 int read(){ 10     int x=0,f=1;char ch=getchar(); 11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();} 13     return x*f; 14 } 15 int nowD; 16 struct node{ 17     int min[2],max[2]; 18     int d[2]; 19     int l,r; 20 }t[mxn<<1]; 21 int root,nct=0; 22 int cmp(const node a,const node b){ 23     if(a.d[nowD]==b.d[nowD])return a.d[nowD^1]<b.d[nowD^1]; 24     return a.d[nowD]<b.d[nowD]; 25 } 26 int qx,qy;//查询参数  27 void pushup(int rt,int c){//更新结点信息  28     t[rt].max[0]=max(t[rt].max[0],t[c].max[0]); 29     t[rt].min[0]=min(t[rt].min[0],t[c].min[0]); 30     t[rt].max[1]=max(t[rt].max[1],t[c].max[1]); 31     t[rt].min[1]=min(t[rt].min[1],t[c].min[1]); 32     return; 33 } 34 int Build(int l,int r,int D){ 35     nowD=D;int mid=(l+r)>>1; 36     nth_element(t+l,t+mid,t+r+1,cmp); 37     t[mid].max[0]=t[mid].min[0]=t[mid].d[0]; 38     t[mid].max[1]=t[mid].min[1]=t[mid].d[1]; 39     if(l!=mid) t[mid].l=Build(l,mid-1,D^1); 40     if(r!=mid) t[mid].r=Build(mid+1,r,D^1); 41     if(t[mid].l)pushup(mid,t[mid].l); 42     if(t[mid].r)pushup(mid,t[mid].r); 43     return mid; 44 } 45 void insert(int x){//插入新结点  46     int now=root,D=0; 47     while(1){ 48         pushup(now,x); 49         if(t[x].d[D]>=t[now].d[D]){ 50             if(!t[now].r){t[now].r=x;return;} 51             else now=t[now].r; 52         } 53         else{ 54             if(!t[now].l){t[now].l=x;return;} 55             else now=t[now].l; 56         } 57         D^=1; 58     } 59     return;  60 } 61 int Dist(int k){//估价  62     int res=0; 63     if(qx<t[k].min[0])res+=t[k].min[0]-qx; 64     if(qx>t[k].max[0])res+=qx-t[k].max[0]; 65     if(qy<t[k].min[1])res+=t[k].min[1]-qy; 66     if(qy>t[k].max[1])res+=qy-t[k].max[1]; 67     return res; 68 } 69 int ans; 70 void query(int rt){ 71     int dx,dy,tmp; 72 //  printf("rt:%d  pos:%d %d ans:%d\n",rt,t[rt].d[0],t[rt].d[1],ans); 73     tmp=abs(t[rt].d[0]-qx)+abs(t[rt].d[1]-qy); 74     if(tmp<ans)ans=tmp; 75     if(t[rt].l) dx=Dist(t[rt].l);else dx=INF; 76     if(t[rt].r) dy=Dist(t[rt].r);else dy=INF; 77     if(dx<dy){ 78         if(dx<ans) query(t[rt].l); 79         if(dy<ans) query(t[rt].r);  80     } 81     else{ 82         if(dy<ans) query(t[rt].r); 83         if(dx<ans) query(t[rt].l);  84     } 85     return; 86 } 87 int n,m; 88 int main(){ 89     int i,j; 90     n=read();m=read(); 91     int T,x,y; 92     for(i=1;i<=n;i++){ 93         t[++nct].d[0]=read(); 94         t[nct].d[1]=read(); 95     } 96     root=Build(1,n,0); 97     while(m--){ 98         T=read();x=read();y=read(); 99         if(T==1){100             t[++nct].d[0]=x; t[nct].d[1]=y;101             t[nct].max[0]=t[nct].min[0]=t[nct].d[0];102             t[nct].max[1]=t[nct].min[1]=t[nct].d[1];103             insert(nct);104         }105         else{106             qx=x;qy=y;ans=INF;107             query(root);108             printf("%d\n",ans);109         }110     }111     return 0;112 }