【BZOJ2716】天使玩偶【kd树】

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <cmath>
  6 using namespace std;
  7 const int maxn=300000+100;
  8 const int INF=2147000000;
  9 
 10 struct kdNode{
 11     int x[2],mnn[2],mxn[2];
 12     int div;
 13     bool lef;
 14 }p[maxn],q;
 15 int n,m,cmpNo;
 16 int lc[maxn],rc[maxn];
 17 int cmp(kdNode a,kdNode b){
 18     return a.x[cmpNo]<b.x[cmpNo];
 19 }
 20 void maintain(int o){
 21     int ls=lc[o],rs=rc[o];
 22     for(int i=0;i<2;i++){
 23         p[o].mnn[i]=min(min(p[ls].mnn[i],p[rs].mnn[i]),p[o].x[i]);
 24         p[o].mxn[i]=max(max(p[ls].mxn[i],p[rs].mxn[i]),p[o].x[i]);
 25     }
 26 }
 27 
 28 void build(int&o,int l,int r,int d){
 29     if(l>r){
 30         o=0;
 31         return;
 32     }
 33     int m=l+(r-l)/2;
 34     cmpNo=d;
 35     nth_element(p+l,p+m,p+r+1,cmp);
 36     o=m;
 37     p[m].div=d;
 38     if(l==r){//好像可以不写
 39         p[m].lef=1;
 40         p[m].mnn[0]=p[m].mxn[0]=p[m].x[0];
 41         p[m].mnn[1]=p[m].mxn[1]=p[m].x[1];
 42         return;
 43     }
 44     build(lc[o],l,m-1,d^1);
 45     build(rc[o],m+1,r,d^1);
 46     maintain(o);
 47 }
 48 int cal(int o){
 49     int res=0;
 50     for(int i=0;i<2;i++)
 51         res+=max(0,p[o].mnn[i]-q.x[i]);
 52     for(int i=0;i<2;i++)
 53         res+=max(0,q.x[i]-p[o].mxn[i]);
 54 }
 55 void Insert(int& o,int d){
 56     if(!o){
 57         o=++n;
 58         p[n]=q;
 59         p[n].div=d;
 60         p[n].lef=1;
 61 //        p[n].mnn[0]=p[n].mxn[0]=p[n].x[0];
 62 //        p[n].mnn[1]=p[n].mxn[1]=p[n].x[1];
 63         return maintain(o);
 64         //return;
 65     }
 66     int t=q.x[d]-p[o].x[d];
 67     if(t>=0){
 68         Insert(rc[o],d^1);
 69     }else{
 70         Insert(lc[o],d^1);
 71     }
 72     maintain(o);
 73 }
 74 int ans;
 75 void query(int o,int d){
 76     if(!o)return;
 77     ans=min(ans,abs(p[o].x[0]-q.x[0])+abs(p[o].x[1]-q.x[1]));
 78     int d1=cal(lc[o]),d2=cal(rc[o]);
 79     if(d2<d1){
 80         query(rc[o],d^1);
 81         if(ans>d1)
 82             query(lc[o],d^1);
 83     }else{
 84         query(lc[o],d^1);
 85         if(ans>d2)
 86             query(rc[o],d^1);
 87     }
 88 }
 89 
 90 int main(){
 91     freopen("in.txt","r",stdin);
 92     freopen("out.txt","w",stdout);
 93     scanf("%d%d",&n,&m);
 94     for(int i=1;i<=n;i++){
 95         scanf("%d%d",&p[i].x[0],&p[i].x[1]);
 96     }
 97     int root;
 98     p[0].mnn[0]=p[0].mnn[1]=INF;
 99     p[0].mxn[0]=p[0].mxn[1]=-INF;
100     build(root,1,n,0);
101     for(int i=1;i<=m;i++){
102         int opt;
103         scanf("%d",&opt);
104         if(opt==1){
105             scanf("%d%d",&q.x[0],&q.x[1]);
106             Insert(root,0);
107         }else{
108             scanf("%d%d",&q.x[0],&q.x[1]);
109             ans=INF;
110             query(root,0);
111             printf("%d\n",ans);
112         }
113     }
114 return 0;
115 }