「BZOJ2716 / 2648」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可以过
题解
由于对K-Dtree理解不足。。。题解先挖坑吧。。我参照了zky神的模板
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define ll long long #define inf 1000000000 using namespace std; inline 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*10+ch-'0';ch=getchar();} return x*f; } int n,m,root,D; struct P{ int d[2],mn[2],mx[2],l,r; int& operator[](int x){return d[x];} P(int x=0,int y=0) {l=0,r=0;d[0]=x,d[1]=y;} }p[500005]; bool operator<(P a,P b) { return a[D]<b[D]; } inline int dis(P a,P b) { return abs(a[0]-b[0])+abs(a[1]-b[1]); } struct kdtree{ int ans; P t[1000005],T; void update(int k){ P l=t[t[k].l],r=t[t[k].r]; for(int i=0;i<2;i++) { if(t[k].l)t[k].mn[i]=min(t[k].mn[i],l.mn[i]),t[k].mx[i]=max(t[k].mx[i],l.mx[i]); if(t[k].r)t[k].mn[i]=min(t[k].mn[i],r.mn[i]),t[k].mx[i]=max(t[k].mx[i],r.mx[i]); } } int build(int l,int r,int now){ D=now; int mid=(l+r)>>1; nth_element(p+l,p+mid,p+r+1); t[mid]=p[mid]; for(int i=0;i<2;i++) t[mid].mn[i]=t[mid].mx[i]=t[mid][i]; if(l<mid)t[mid].l=build(l,mid-1,now^1); if(r>mid)t[mid].r=build(mid+1,r,now^1); update(mid); return mid; } int get(int k,P p){ int tmp=0; for(int i=0;i<2;i++) tmp+=max(0,t[k].mn[i]-p[i]); for(int i=0;i<2;i++) tmp+=max(0,p[i]-t[k].mx[i]); return tmp; } void insert(int k,int now){ if(T[now]>=t[k][now]) { if(t[k].r)insert(t[k].r,now^1); else { t[k].r=++n;t[n]=T; for(int i=0;i<2;i++) t[n].mn[i]=t[n].mx[i]=t[n][i]; } } else { if(t[k].l)insert(t[k].l,now^1); else { t[k].l=++n;t[n]=T; for(int i=0;i<2;i++) t[n].mn[i]=t[n].mx[i]=t[n][i]; } } update(k); } void query(int k,int now){ int d,dl=inf,dr=inf; d=dis(t[k],T); ans=min(ans,d); if(t[k].l)dl=get(t[k].l,T); if(t[k].r)dr=get(t[k].r,T); if(dl<dr) { if(dl<ans)query(t[k].l,now^1); if(dr<ans)query(t[k].r,now^1); } else { if(dr<ans)query(t[k].r,now^1); if(dl<ans)query(t[k].l,now^1); } } int query(P p){ ans=inf;T=p;query(root,0); return ans; } void insert(P p){ T=p;insert(root,0); } }kd; int main() { n=read();m=read(); for(int i=1;i<=n;i++)p[i][0]=read(),p[i][1]=read(); root=kd.build(1,n,0); while(m--) { int opt=read(),x=read(),y=read(); if(opt==1)kd.insert(P(x,y)); else printf("%d\n",kd.query(P(x,y))); } return 0; } |
计数器 9790736
OI 课件=>
OI 课件=>
1 2
0 0
1 1 -1
2 -2 1
强。。。
天使玩偶坐标都是非负数我就没读入符号
我当时貌似是代码挂了，拿你的对拍……233
K-DTree最高搞到多少维啊？？
n维