SJY摆棋子
Time Limit: 20 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
Description
这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N个初始棋子，和M个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。
Input
第一行两个数 N M
然后N行，每行2个数 x y，表示初始棋子
以后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
N<=500000 , M<=500000
Main idea
在平面上加入黑点，对于询问一个坐标到其它点的曼哈顿距离中最小的一个。
Solution
这题显然是一道KD-tree的模板题。
我们来考虑如何估价，由于求的是最小的曼哈顿距离，我们可以这样估价：
（其实我也并不懂为什么可以这样估，详情可以查询“n+e KDtree在信息学奥赛中的应用”）
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
using namespace std; const int ONE=;
const int INF=; int n,m;
int t,x,y;
int cnt,Ans;
int root;
int Ran; struct power
{
int l,r;
int x,y;
int minx,miny;
int maxx,maxy;
}a[ONE]; int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} namespace KD
{
void Update(int i)
{
if(a[i].l)
{
a[i].minx=min(a[i].minx,a[a[i].l].minx); a[i].miny=min(a[i].miny,a[a[i].l].miny);
a[i].maxx=max(a[i].maxx,a[a[i].l].maxx); a[i].maxy=max(a[i].maxy,a[a[i].l].maxy);
}
if(a[i].r)
{
a[i].minx=min(a[i].minx,a[a[i].r].minx); a[i].miny=min(a[i].miny,a[a[i].r].miny);
a[i].maxx=max(a[i].maxx,a[a[i].r].maxx); a[i].maxy=max(a[i].maxy,a[a[i].r].maxy);
}
} int cmp(const power &a,const power &b)
{
if(Ran) return a.x<b.x;
return a.y<b.y;
} int Build(int l,int r,int T)
{
int mid=(l+r)/;
Ran=T;
nth_element(a+l, a+mid+, a+r+, cmp);
if(l<mid) a[mid].l = Build(l,mid-,T^);
if(mid<r) a[mid].r = Build(mid+,r,T^);
Update(mid);
return mid;
}
} void Update(int &i,int x,int y,int T)
{
if(!i)
{
i=++cnt;
a[i].x=a[i].minx=a[i].maxx=x;
a[i].y=a[i].miny=a[i].maxy=y;
return;
} if(T)
{
if(x < a[i].x) Update(a[i].l,x,y,T^);
else Update(a[i].r,x,y,T^);
KD::Update(i);
}
else
{
if(y < a[i].y) Update(a[i].l,x,y,T^);
else Update(a[i].r,x,y,T^);
KD::Update(i);
}
} int dist(int x1,int y1,int x2,int y2)
{
return abs(x1-x2)+abs(y1-y2);
} int dist(int i,int x,int y)
{
return max(a[i].minx-x,)+max(x-a[i].maxx,) + max(a[i].miny-y,)+max(y-a[i].maxy,);
} void Query(int i,int x,int y)
{
if(!i) return;
Ans=min(Ans,dist(x,y , a[i].x,a[i].y));
int l=dist(a[i].l,x,y);
int r=dist(a[i].r,x,y);
if(l<r)
{
if(l<=Ans) Query(a[i].l,x,y);
if(r<=Ans) Query(a[i].r,x,y);
}
else
{
if(r<=Ans) Query(a[i].r,x,y);
if(l<=Ans) Query(a[i].l,x,y);
}
} int main()
{
n=get(); m=get();
for(int i=;i<=n;i++)
{
x=get(); y=get();
a[i].x=a[i].minx=a[i].maxx=x;
a[i].y=a[i].miny=a[i].maxy=y;
} cnt=n;
root=KD::Build(,n,); for(int i=;i<=m;i++)
{
t=get(); x=get(); y=get();
if(t==)
{
n++;
a[n].x=a[n].minx=a[n].maxx=x;
a[n].y=a[n].miny=a[n].maxy=y;
Update(root,x,y,);
}
else
{
Ans=INF;
Query(root,x,y);
printf("%d\n",Ans);
}
}
}