[文章目录]
Description
这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。
KD-tree模板题。
根据GXZlegend的授课：对于KD-tree维护二维平面上和定点的最近距离，只有切比雪夫距离没有被GXZlegend卡掉（曼哈顿以及欧几里得距离都被卡成n^2）
我们将曼哈顿距离转成切比雪夫距离：(x,y)->(x+y,x-y)之后拿KD-tree维护就好啦。时间复杂度O(n√n)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
inline int Abs(int x){return x>0?x:-x;}
int rot,d,ans;
struct KD_tree
{
int c[2],mx[2],mi[2],p[2];
}t[1001000];
bool operator < (KD_tree x,KD_tree y)
{
return x.p[d]==y.p[d] ? x.p[d^1]<y.p[d^1] : x.p[d]<y.p[d];
}
void pushup(int p,int s)
{
t[p].mx[0]=max(t[p].mx[0],t[s].mx[0]);
t[p].mx[1]=max(t[p].mx[1],t[s].mx[1]);
t[p].mi[0]=min(t[p].mi[0],t[s].mi[0]);
t[p].mi[1]=min(t[p].mi[1],t[s].mi[1]);
}
int build(int l,int r,int now)
{
int mid=(l+r)>>1;
d=now; nth_element(t+l,t+mid,t+r+1);
t[mid].mx[0]=t[mid].mi[0]=t[mid].p[0];
t[mid].mx[1]=t[mid].mi[1]=t[mid].p[1];
if(l<mid) t[mid].c[0]=build(l,mid-1,now^1),pushup(mid,t[mid].c[0]);
if(r>mid) t[mid].c[1]=build(mid+1,r,now^1),pushup(mid,t[mid].c[1]);
return mid;
}
void ins(int k)
{
int *p=&rot;
d=0;
while(*p) pushup(*p,k),p=&t[*p].c[ t[k].p[d] > t[*p].p[d] ],d^=1;
*p=k;
}
inline int getdis(int k,int x,int y)
{
int re=0;
if(x<t[k].mi[0]) re=max(re,t[k].mi[0]-x);
else if(x>t[k].mx[0]) re=max(re,x-t[k].mx[0]);
if(y<t[k].mi[1]) re=max(re,t[k].mi[1]-y);
else if(y>t[k].mx[1]) re=max(re,y-t[k].mx[1]);
return re;
}
void query(int k,int x,int y)
{
int dn=max( Abs(t[k].p[0]-x),Abs(t[k].p[1]-y) ),dl,dr;
if(dn<ans) ans=dn;
dl=t[k].c[0] ? getdis(t[k].c[0],x,y) : inf;
dr=t[k].c[1] ? getdis(t[k].c[1],x,y) : inf;
if(dl<dr)
{
if(dl<ans) query(t[k].c[0],x,y);
if(dr<ans) query(t[k].c[1],x,y);
}
else
{
if(dr<ans) query(t[k].c[1],x,y);
if(dl<ans) query(t[k].c[0],x,y);
}
}
int main()
{
int n,m,i,sw,x,y;
read(n); read(m);
for(i=1;i<=n;++i)
{
read(x); read(y);
t[i].p[0]=x+y;
t[i].p[1]=x-y;
}
rot=build(1,n,0);
while(m--)
{
read(sw); read(x); read(y);
x=x+y; y=x-(y<<1);
switch(sw)
{
case 1:
{
++n;
t[n].p[0]=t[n].mx[0]=t[n].mi[0]=x;
t[n].p[1]=t[n].mx[1]=t[n].mi[1]=y;
ins(n);
break;
}
default:
{
ans=inf;
query(rot,x,y);
printf("%d\n",ans);
}
}
}
return 0;
}