[BZOJ2648] SJY摆棋子 kd-tree

2648: SJY摆棋子

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 5421 Solved: 1910
[Submit][Status][Discuss]

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

鸣谢孙嘉裕

kd-tree裸题

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #define maxn 1000001

 using namespace std;

 struct data {

     int mn[],mx[],l,r,d[];

     data() {mn[]=mn[]=mx[]=mx[]=l=r=d[]=d[]=;}

 }t[maxn*];

 int n,m;

 int nowd;

 bool cmp(data t1,data t2) {return t1.d[nowd]==t2.d[nowd]?t1.d[!nowd]<t2.d[!nowd]:t1.d[nowd]<t2.d[nowd];}

 void update(int x) {

     if(t[x].l) {

         t[x].mx[]=max(t[x].mx[],t[t[x].l].mx[]);

         t[x].mn[]=min(t[x].mn[],t[t[x].l].mn[]);

         t[x].mx[]=max(t[x].mx[],t[t[x].l].mx[]);

         t[x].mn[]=min(t[x].mn[],t[t[x].l].mn[]);

     }

     if(t[x].r) {

         t[x].mx[]=max(t[x].mx[],t[t[x].r].mx[]);

         t[x].mn[]=min(t[x].mn[],t[t[x].r].mn[]);

         t[x].mx[]=max(t[x].mx[],t[t[x].r].mx[]);

         t[x].mn[]=min(t[x].mn[],t[t[x].r].mn[]);

     }

 }

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

     int mid=l+r>>;

     nowd=D;

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

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

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

     t[mid].mx[]=t[mid].mn[]=t[mid].d[];

     t[mid].mx[]=t[mid].mn[]=t[mid].d[];

     update(mid);

     return mid;

 }

 void insert(int &now,int D,data x) {

     if(!now) {now=++n;t[now]=x;t[now].mn[]=t[now].mx[]=x.d[];t[now].mx[]=t[now].mn[]=x.d[];return;}

     if(x.d[D]>t[now].d[D]) insert(t[now].r,!D,x);

     else insert(t[now].l,!D,x);

     update(now);

 }

 int dis(int now,data x) {

     int re=;

     if(x.d[]<t[now].mn[]) re+=t[now].mn[]-x.d[];

     if(x.d[]>t[now].mx[]) re+=x.d[]-t[now].mx[];

     if(x.d[]<t[now].mn[]) re+=t[now].mn[]-x.d[];

     if(x.d[]>t[now].mx[]) re+=x.d[]-t[now].mx[];

     return re;

 }

 int ans;

 void query(int now,data x) {

     ans=min(ans,abs(t[now].d[]-x.d[])+abs(t[now].d[]-x.d[]));

     int dl,dr;

     if(t[now].l) dl=dis(t[now].l,x); else dl=;

     if(t[now].r) dr=dis(t[now].r,x); else dr=;

     if(dl<dr) {

         if(dl<ans) query(t[now].l,x);

         if(dr<ans) query(t[now].r,x);

     }

     else {

         if(dr<ans) query(t[now].r,x);

         if(dl<ans) query(t[now].l,x);

     }

 }

 int main() {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%d%d",&t[i].d[],&t[i].d[]);

     int mid=build(,n,);

     for(int i=;i<=m;i++) {

         int tp;data x;

         scanf("%d%d%d",&tp,&x.d[],&x.d[]);

         if(tp==) insert(mid,,x);

         else {ans=;query(mid,x);printf("%d\n",ans);}

     }

 }

巴特西