首页 > 代码库 > bzoj2648 SJY摆棋子
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
1 1
2 3
2 1 2
1 3 3
2 4 2
Sample Output
1
2
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\n",ans);109 }110 return;111 }112 113 int main(){114 File("SJY");115 work();116 return 0;117 }
bzoj2648 SJY摆棋子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。