【BZOJ2648】SJY摆棋子（KD-Tree）
题面
BZOJ
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
题解
\(KD-Tree\)模板题？
对于分割出来的矩阵，维护矩阵中的点的两维坐标的最大和最小值
这样就可以计算当前点到达这个矩阵的最短距离
这样就可以剪枝啦
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 555555
#define ls (t[x].ch[0])
#define rs (t[x].ch[1])
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
inline int read()
{RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t;
}
int D;
int n,rt,Q;
struct Node{int d[2];}a[MAX];
bool operator<(Node a,Node b){return a.d[D]<b.d[D];}
struct KD_Tree_Node
{int d[2],mn[2],mx[2];int ch[2];
}t[MAX<<1];
int ans;
void update(int x,int y)
{cmin(t[x].mn[0],t[y].mn[0]);cmin(t[x].mn[1],t[y].mn[1]);cmax(t[x].mx[0],t[y].mx[0]);cmax(t[x].mx[1],t[y].mx[1]);
}
int Build(int l,int r,int nD)
{int x=(l+r)>>1;D=nD;nth_element(&a[l],&a[x],&a[r+1]);t[x].d[0]=t[x].mn[0]=t[x].mx[0]=a[x].d[0];t[x].d[1]=t[x].mn[1]=t[x].mx[1]=a[x].d[1];if(l<x)ls=Build(l,x-1,nD^1),update(x,ls);if(r>x)rs=Build(x+1,r,nD^1),update(x,rs);return x;
}
int Dist(int nw,int X,int Y)
{return max(t[nw].mn[0]-X,0)+max(X-t[nw].mx[0],0)+max(t[nw].mn[1]-Y,0)+max(Y-t[nw].mx[1],0);
}
void Query(int x,int xx,int yy)
{int tmp=abs(t[x].d[0]-xx)+abs(t[x].d[1]-yy),d[2];d[0]=ls?Dist(ls,xx,yy):2e9;d[1]=rs?Dist(rs,xx,yy):2e9;cmin(ans,tmp);tmp=d[0]>=d[1];if(d[tmp]<ans)Query(t[x].ch[tmp],xx,yy);if(d[tmp^1]<ans)Query(t[x].ch[tmp^1],xx,yy);
}
int main()
{n=read();Q=read();for(int i=1;i<=n;++i)a[i].d[0]=read(),a[i].d[1]=read();rt=Build(1,n,0);while(Q--){int opt=read(),x=read(),y=read();if(opt==1){++n;t[n].d[0]=t[n].mn[0]=t[n].mx[0]=x;t[n].d[1]=t[n].mn[1]=t[n].mx[1]=y;for(int nw=rt,d=0;nw;d^=1){update(nw,n);int k=t[n].d[d]>=t[nw].d[d];if(!t[nw].ch[k]){t[nw].ch[k]=n;break;}nw=t[nw].ch[k];}}else{ans=2e9;Query(rt,x,y);printf("%d\n",ans);}}return 0;
}
上面是不会重建\(KD-Tree\)的代码
洛谷上数据有所加强，这样做会\(TLE\)
所以考虑替罪羊树类似的重构即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 555555
#define ls (t[x].ch[0])
#define rs (t[x].ch[1])
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
inline int read()
{RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t;
}
const double alpha=0.75;
int D;
int n,rt,m;
struct Node{int d[2];}a[MAX];
bool operator<(Node a,Node b){return a.d[D]<b.d[D];}
struct KD_Tree_Node
{int d[2],mn[2],mx[2];int ch[2],size;
}t[MAX<<1];
int ans;
int Q[MAX<<1],top,tot;
int Num;
int NewNode()
{if(!top)return ++tot;return Q[top--];
}
void update(int x,int y)
{cmin(t[x].mn[0],t[y].mn[0]);cmin(t[x].mn[1],t[y].mn[1]);cmax(t[x].mx[0],t[y].mx[0]);cmax(t[x].mx[1],t[y].mx[1]);
}
void pushup(int x)
{t[x].mn[0]=t[x].mx[0]=t[x].d[0];t[x].mn[1]=t[x].mx[1]=t[x].d[1];t[x].size=t[ls].size+t[rs].size+1;if(ls)update(x,ls);if(rs)update(x,rs);
}
int Build(int l,int r,int nD)
{int mid=(l+r)>>1;D=nD;nth_element(&a[l],&a[mid],&a[r+1]);int x=NewNode();t[x].d[0]=a[mid].d[0];t[x].d[1]=a[mid].d[1];if(l<mid)ls=Build(l,mid-1,nD^1);else ls=0;if(r>mid)rs=Build(mid+1,r,nD^1);else rs=0;pushup(x);return x;
}
int Dist(int nw,int X,int Y)
{return max(t[nw].mn[0]-X,0)+max(X-t[nw].mx[0],0)+max(t[nw].mn[1]-Y,0)+max(Y-t[nw].mx[1],0);
}
void Query(int x,int xx,int yy)
{int tmp=abs(t[x].d[0]-xx)+abs(t[x].d[1]-yy),d[2];d[0]=ls?Dist(ls,xx,yy):2e9;d[1]=rs?Dist(rs,xx,yy):2e9;cmin(ans,tmp);tmp=d[0]>=d[1];if(d[tmp]<ans)Query(t[x].ch[tmp],xx,yy);if(d[tmp^1]<ans)Query(t[x].ch[tmp^1],xx,yy);
}
void kill(int x){if(ls)kill(ls);a[++Num]=(Node){t[x].d[0],t[x].d[1]};Q[++top]=x;if(rs)kill(rs);}
void check(int &x,int nd)
{if(t[x].size*alpha<t[ls].size||t[x].size*alpha<t[rs].size)Num=0,kill(x),x=Build(1,Num,nd);
}
void insert(int &x,Node a,int nd)
{if(!x){x=NewNode();t[x].d[0]=a.d[0];t[x].d[1]=a.d[1];pushup(x);return;}if(a.d[nd]>t[x].d[nd])insert(rs,a,nd^1);else insert(ls,a,nd^1);pushup(x);check(x,nd);
}
int main()
{n=read();m=read();for(int i=1;i<=n;++i)a[i].d[0]=read(),a[i].d[1]=read();rt=Build(1,n,0);while(m--){int opt=read(),x=read(),y=read();if(opt==1)insert(rt,(Node){x,y},0);else{ans=2e9;Query(rt,x,y);printf("%d\n",ans);}}return 0;
}
