Bzoj2648 SJY摆棋子

Time Limit: 20 Sec Memory Limit: 128 MB

Submit: 3128 Solved: 1067

Description

这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M

以后M行，每行3个数 t x y

如果t=1 那么放下一个黑色棋子

如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output

1
2

HINT

kdtree可以过

Source

鸣谢孙嘉裕

K-Dtree模板题

似乎有种懂了的错觉

(錯覚？それでは、聞いてください....)

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int INF=1e9;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}

     return x*f;

 }

 int nowD;

 struct node{

     int min[],max[];

     int d[];

     int l,r;

 }t[mxn<<];

 int root,nct=;

 int cmp(const node a,const node b){

     if(a.d[nowD]==b.d[nowD])return a.d[nowD^]<b.d[nowD^];

     return a.d[nowD]<b.d[nowD];

 }

 int qx,qy;//查询参数

 void pushup(int rt,int c){//更新结点信息

     t[rt].max[]=max(t[rt].max[],t[c].max[]);

     t[rt].min[]=min(t[rt].min[],t[c].min[]);

     t[rt].max[]=max(t[rt].max[],t[c].max[]);

     t[rt].min[]=min(t[rt].min[],t[c].min[]);

     return;

 }

 int Build(int l,int r,int D){

     nowD=D;int mid=(l+r)>>;

     nth_element(t+l,t+mid,t+r+,cmp);

     t[mid].max[]=t[mid].min[]=t[mid].d[];

     t[mid].max[]=t[mid].min[]=t[mid].d[];

     if(l!=mid) t[mid].l=Build(l,mid-,D^);

     if(r!=mid) t[mid].r=Build(mid+,r,D^);

     if(t[mid].l)pushup(mid,t[mid].l);

     if(t[mid].r)pushup(mid,t[mid].r);

     return mid;

 }

 void insert(int x){//插入新结点

     int now=root,D=;

     while(){

         pushup(now,x);

         if(t[x].d[D]>=t[now].d[D]){

             if(!t[now].r){t[now].r=x;return;}

             else now=t[now].r;

         }

         else{

             if(!t[now].l){t[now].l=x;return;}

             else now=t[now].l;

         }

         D^=;

     }

     return;

 }

 int Dist(int k){//估价

     int res=;

     if(qx<t[k].min[])res+=t[k].min[]-qx;

     if(qx>t[k].max[])res+=qx-t[k].max[];

     if(qy<t[k].min[])res+=t[k].min[]-qy;

     if(qy>t[k].max[])res+=qy-t[k].max[];

     return res;

 }

 int ans;

 void query(int rt){

     int dx,dy,tmp;

 //  printf("rt:%d  pos:%d %d ans:%d\n",rt,t[rt].d[0],t[rt].d[1],ans);

     tmp=abs(t[rt].d[]-qx)+abs(t[rt].d[]-qy);

     if(tmp<ans)ans=tmp;

     if(t[rt].l) dx=Dist(t[rt].l);else dx=INF;

     if(t[rt].r) dy=Dist(t[rt].r);else dy=INF;

     if(dx<dy){

         if(dx<ans) query(t[rt].l);

         if(dy<ans) query(t[rt].r);

     }

     else{

         if(dy<ans) query(t[rt].r);

         if(dx<ans) query(t[rt].l);

     }

     return;

 }

 int n,m;

 int main(){

     int i,j;

     n=read();m=read();

     int T,x,y;

     for(i=;i<=n;i++){

         t[++nct].d[]=read();

         t[nct].d[]=read();

     }

     root=Build(,n,);

     while(m--){

         T=read();x=read();y=read();

         if(T==){

             t[++nct].d[]=x; t[nct].d[]=y;

             t[nct].max[]=t[nct].min[]=t[nct].d[];

             t[nct].max[]=t[nct].min[]=t[nct].d[];

             insert(nct);

         }

         else{

             qx=x;qy=y;ans=INF;

             query(root);

             printf("%d\n",ans);

         }

     }

     return ;

 }

巴特西