bzoj2648 SJY摆棋子

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可以过

正解：$kd-tree$。

一个暴力的数据结构——$kd-tree$。。

类似于平面分治，我们按照横坐标和纵坐标交替二分平面区域。

取当前维坐标的中点，不断往下递归建树，维护当前点所构成的$kd-tree$的平面区域，即横坐标和纵坐标的最小最大值。记录每个点的左儿子和右儿子。

插入结点时，如果到底了就直接新建，否则如果当前维坐标小于根就往左走，否则往右走，类似于$BST$。

查询的时候直接比较当前点左右子树的区域到查询点的距离是否大于$ans$，如果是则直接剪掉，否则就往下搜。注意这里有一个细微的剪枝，看下代码吧。我把这个剪枝去掉以后就$T$了。。

总之这就是个乱搞的数据结构，快不快就看你剪枝好不好。

  1 //It is made by wfj_2048~
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <cstdio>
  7 #include <vector>
  8 #include <cmath>
  9 #include <queue>
 10 #include <stack>
 11 #include <map>
 12 #include <set>
 13 #define inf (1<<30)
 14 #define N (1000010)
 15 #define il inline
 16 #define RG register
 17 #define ll long long
 18 #define fi01() for (RG int i=0;i<=1;++i)
 19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
 20 
 21 using namespace std;
 22 
 23 int K,n,m,x,y,op,rt,ans;
 24 
 25 struct node{
 26     
 27     int a[2],mn[2],mx[2],l,r;
 28     
 29     bool operator < (const node &t) const{
 30     return a[K]<t.a[K];
 31     }
 32     
 33 }t[N],S;
 34 
 35 il int gi(){
 36     RG int x=0,q=1; RG char ch=getchar();
 37     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
 38     if (ch=='-') q=-1,ch=getchar();
 39     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
 40     return q*x;
 41 }
 42 
 43 il void merge(RG int x){
 44     fi01(){
 45     if (t[x].l){
 46         t[x].mn[i]=min(t[x].mn[i],t[t[x].l].mn[i]);
 47         t[x].mx[i]=max(t[x].mx[i],t[t[x].l].mx[i]);
 48     }
 49     if (t[x].r){
 50         t[x].mn[i]=min(t[x].mn[i],t[t[x].r].mn[i]);
 51         t[x].mx[i]=max(t[x].mx[i],t[t[x].r].mx[i]);
 52     }
 53     }
 54     return;
 55 }
 56 
 57 il int get(RG int x){
 58     if (!x) return inf; RG int res=0;
 59     fi01() res+=max(0,t[x].mn[i]-S.a[i])+max(0,S.a[i]-t[x].mx[i]);
 60     return res;
 61 }
 62 
 63 il int build(RG int l,RG int r,RG int p){
 64     K=p; RG int mid=(l+r)>>1; nth_element(t+l,t+mid,t+r+1);
 65     fi01() t[mid].mn[i]=t[mid].mx[i]=t[mid].a[i];
 66     if (l<mid) t[mid].l=build(l,mid-1,p^1);
 67     if (r>mid) t[mid].r=build(mid+1,r,p^1);
 68     merge(mid); return mid;
 69 }
 70 
 71 il void insert(RG int x,RG int p){
 72     K=p;
 73     if (S<t[x]){
 74     if (t[x].l) insert(t[x].l,p^1); else{
 75         t[t[x].l=++n]=S;
 76         fi01() t[n].mn[i]=t[n].mx[i]=t[n].a[i];
 77     }
 78     } else{
 79     if (t[x].r) insert(t[x].r,p^1); else{
 80         t[t[x].r=++n]=S;
 81         fi01() t[n].mn[i]=t[n].mx[i]=t[n].a[i];
 82     }
 83     }
 84     merge(x); return;
 85 }
 86 
 87 il void query(RG int x){
 88     ans=min(ans,abs(S.a[0]-t[x].a[0])+abs(S.a[1]-t[x].a[1]));
 89     RG int dl=get(t[x].l),dr=get(t[x].r);
 90     if (dl<dr){
 91     if (dl<ans) query(t[x].l);
 92     if (dr<ans) query(t[x].r);
 93     } else{
 94     if (dr<ans) query(t[x].r);
 95     if (dl<ans) query(t[x].l);
 96     }
 97     return;
 98 }
 99 
100 il void work(){
101     n=gi(),m=gi();
102     for (RG int i=1;i<=n;++i) t[i].a[0]=gi(),t[i].a[1]=gi();
103     rt=build(1,n,0);
104     while (m--){
105     op=gi(),S.a[0]=gi(),S.a[1]=gi();
106     S.l=S.r=S.mn[0]=S.mn[1]=S.mx[0]=S.mx[1]=0;
107     if (op==1) insert(rt,0);
108     else ans=inf,query(rt),printf("%d
",ans);
109     }
110     return;
111 }
112 
113 int main(){
114     File("SJY");
115     work();
116     return 0;
117 }