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
1 1
2 3
2 1 2
1 3 3
2 4 2
Sample Output
1
2
HINT
kdtree可以过
Source
鸣谢 孙嘉裕
KDtree~
个人理解:
KDtree是一种二叉树,每个节点是一条分割线,把区间分为两段。
每个节点有4种:a[2],mn[2],mx[2],l,r,分别记录该点坐标,代表区间的最小横纵坐标,代表区间的最大横纵坐标,以及左右区间坐标。
然后,在查询时每次记录目前最小距离,查询左右区间里面最大最小坐标形成的区间与查询点的差的最小值(如果在其中则为0),如果答案大于这个最小值,就向下搜索更新答案。
nth_element(a+l,a+k,a+r+1)相当神奇,把第k大的数放到第k个位置上,前面的小于它,后面的大于它,但前后分别为乱序,复杂度比sort()要低,需要头文件algorithm~
(函数里面少传了一个参数,就快了1s……传参常数好大啊)
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 999999999int n,m,opt,x,y,root,kkz,ans;struct node{int a[2],mx[2],mn[2],l,r;
}a[500001],c[1000001],kkzv,T;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}bool operator < (node u,node v)
{return u.a[kkz]<v.a[kkz];
}int abs(int u)
{return u<0 ? -u:u;
}int dis(node u,node v)
{return abs(u.a[0]-v.a[0])+abs(u.a[1]-v.a[1]);
}void update(int u)
{node l=c[c[u].l],r=c[c[u].r];for(int i=0;i<2;i++){if(c[u].l) c[u].mx[i]=max(c[u].mx[i],l.mx[i]),c[u].mn[i]=min(c[u].mn[i],l.mn[i]);if(c[u].r) c[u].mx[i]=max(c[u].mx[i],r.mx[i]),c[u].mn[i]=min(c[u].mn[i],r.mn[i]);}
}int build(int l,int r,int now)
{kkz=now;int mid=l+r>>1;nth_element(a+l,a+mid,a+r+1);c[mid]=a[mid];for(int i=0;i<2;i++) c[mid].mn[i]=c[mid].mx[i]=c[mid].a[i];if(l<mid) c[mid].l=build(l,mid-1,now^1);if(r>mid) c[mid].r=build(mid+1,r,now^1);update(mid);return mid;
}int get(int k,node u)
{int now=0;for(int i=0;i<2;i++) now+=max(0,c[k].mn[i]-u.a[i]);for(int i=0;i<2;i++) now+=max(0,u.a[i]-c[k].mx[i]);return now;
}void insert(int k,int now)
{if(T.a[now]>=c[k].a[now]){if(c[k].r) insert(c[k].r,now^1);else {c[k].r=++n;c[n]=T;for(int i=0;i<2;i++) c[n].mn[i]=c[n].mx[i]=c[n].a[i];}}else {if(c[k].l) insert(c[k].l,now^1);else {c[k].l=++n;c[n]=T;for(int i=0;i<2;i++) c[n].mn[i]=c[n].mx[i]=c[n].a[i];}}update(k);
}void query(int k)
{int d,dl=inf,dr=inf;d=dis(c[k],T);ans=min(ans,d);if(c[k].l) dl=get(c[k].l,T);if(c[k].r) dr=get(c[k].r,T);if(dl<dr){if(dl<ans) query(c[k].l);if(dr<ans) query(c[k].r);}else{if(dr<ans) query(c[k].r);if(dl<ans) query(c[k].l);}
}int query(node p)
{ans=inf;T=p;query(root);return ans;
}int main()
{n=read();m=read();for(int i=1;i<=n;i++) a[i].a[0]=read(),a[i].a[1]=read();root=build(1,n,0);while(m--){opt=read();kkzv.a[0]=read();kkzv.a[1]=read();if(opt==1) T=kkzv,insert(root,0);else printf("%d\n",query(kkzv));}return 0;
}