【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
题解：初学KDtree，感兴趣的可以看一下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define rep for(i=0;i<=1;i++)
using namespace std;
struct KD
{
int ls,rs,v[2],sn[2],sm[2];
KD (int a,int b){ls=rs=0,sn[0]=sm[0]=v[0]=a,sn[1]=sm[1]=v[1]=b;}
KD (){}
}t[1000010];
int D,n,m,tot,ans,root;
bool cmp(KD a,KD b)
{
if(a.v[D]==b.v[D]) return a.v[D^1]<b.v[D^1];
return a.v[D]<b.v[D];
}
void pushup(int x,int y)
{
int i;
rep t[x].sn[i]=min(t[x].sn[i],t[y].sn[i]),t[x].sm[i]=max(t[x].sm[i],t[y].sm[i]);
}
int getdis(int x,int y)
{
int ret=0,i;
rep ret+=max(t[x].sn[i]-t[y].v[i],0)+max(t[y].v[i]-t[x].sm[i],0);
return ret;
}
int build(int l,int r,int d)
{
if(l>r) return 0;
D=d;
int mid=l+r>>1;
nth_element(t+l,t+mid,t+r+1,cmp);
t[mid].ls=build(l,mid-1,d^1);
t[mid].rs=build(mid+1,r,d^1);
if(t[mid].ls) pushup(mid,t[mid].ls);
if(t[mid].rs) pushup(mid,t[mid].rs);
return mid;
}
void insert(int y)
{
int x=root;
D=0;
while(1)
{
pushup(x,y);
if(t[y].v[D]<t[x].v[D])
{
if(t[x].ls) x=t[x].ls;
else {t[x].ls=y,pushup(x,y); break;}
}
else
{
if(t[x].rs) x=t[x].rs;
else {t[x].rs=y,pushup(x,y); break;}
}
D^=1;
}
}
void query(int x,int y)
{
if(!x||getdis(x,y)>ans) return ;
ans=min(ans,abs(t[x].v[0]-t[y].v[0])+abs(t[x].v[1]-t[y].v[1]));
if(!(t[x].ls*t[x].rs))
{
query(t[x].ls^t[x].rs,y);
return ;
}
int dl=getdis(t[x].ls,y),dr=getdis(t[x].rs,y);
if(dl<dr) query(t[x].ls,y),query(t[x].rs,y);
else query(t[x].rs,y),query(t[x].ls,y);
}
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i,a,b,c;
for(i=1;i<=n;i++) a=rd(),b=rd(),t[i]=KD(a,b);
root=build(1,n,0);
for(i=1;i<=m;i++)
{
a=rd(),b=rd(),c=rd(),t[i+n]=KD(b,c);
if(a==1) insert(i+n);
else ans=1<<30,query(root,i+n),printf("%d\n",ans);
}
return 0;
}