SJY摆旗子 bzoj-2648
题目大意：平面上有n个黑子。有m个操作，可以下一颗白子，查询与曼哈顿距离下最近黑子之间的曼哈顿距离，或者下一颗黑子。
注释：$1le n,mle 5cdot 10^5$
想法：KD-Tree维护近邻点对问题。
这类问题和那个定区域查询问题不一样，那个问题的查询是类似分治，而近邻点对这个其实就是启发式暴力..
设一个估价函数，表示当前要查询的点到矩阵的估价距离。
这个估价函数是容易的，如果这个点在矩形里就是0，否则就是矩阵的4个顶点距离该店曼哈顿距离小的曼哈顿距离。
这样考虑先遍历左子树还是右子树。如果估价函数比当前答案还大，就不遍历了。
然后这个问题有插入操作，如果KD-Tree有插入操作，我们一般会在左右size差在一个值的时候重构或者直接插入多少次重构。
这个题不用。
最后，附上丑陋的代码... ...
#include <cstdio>
#include <algorithm>
#define inf 0x7f7f7f7f
#define N 1000010
using namespace std;
int ans,root,d;
struct Node
{
int p[2],maxn[2],minn[2],c[2];
}a[N];
inline bool cmp(const Node &a,const Node &b)
{
return a.p[d]==b.p[d]?a.p[d^1]<b.p[d^1]:a.p[d]<b.p[d];
}
void pushup(int k,int s)
{
a[k].maxn[0]=max(a[k].maxn[0],a[s].maxn[0]);
a[k].maxn[1]=max(a[k].maxn[1],a[s].maxn[1]);
a[k].minn[0]=min(a[k].minn[0],a[s].minn[0]);
a[k].minn[1]=min(a[k].minn[1],a[s].minn[1]);
}
int build(int l,int r,int now)
{
int mid=(l+r)>>1;
d=now,nth_element(a+l,a+mid,a+r+1,cmp);
a[mid].maxn[0]=a[mid].minn[0]=a[mid].p[0];
a[mid].maxn[1]=a[mid].minn[1]=a[mid].p[1];
if(l<mid) a[mid].c[0]=build(l,mid-1,now^1),pushup(mid,a[mid].c[0]);
if(mid<r) a[mid].c[1]=build(mid+1,r,now^1),pushup(mid,a[mid].c[1]);
return mid;
}
void ins(int k)
{
int *t=&root;
d=0;
while(*t) pushup(*t,k),t=&a[*t].c[a[k].p[d]>a[*t].p[d]],d^=1;
*t=k;
}
int getdis(int k,int x,int y)
{
int ans=0;
if(x<a[k].minn[0]) ans+=a[k].minn[0]-x;
if(x>a[k].maxn[0]) ans+=x-a[k].maxn[0];
if(y<a[k].minn[1]) ans+=a[k].minn[1]-y;
if(y>a[k].maxn[1]) ans+=y-a[k].maxn[1];
return ans;
}
void query(int k,int x,int y)
{
int dn=abs(x-a[k].p[0])+abs(y-a[k].p[1]),dl,dr;
ans=min(ans,dn);
dl=a[k].c[0]?getdis(a[k].c[0],x,y):inf;
dr=a[k].c[1]?getdis(a[k].c[1],x,y):inf;
if(dl<dr)
{
if(dl<ans) query(a[k].c[0],x,y);
if(dr<ans) query(a[k].c[1],x,y);
}
else
{
if(dr<ans) query(a[k].c[1],x,y);
if(dl<ans) query(a[k].c[0],x,y);
}
}
int main()
{
int n,m,opt,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].p[0],&a[i].p[1]);
root=build(1,n,0);
while(m--)
{
scanf("%d%d%d",&opt,&x,&y);
if(opt==1) n++,a[n].p[0]=a[n].maxn[0]=a[n].minn[0]=x,a[n].p[1]=a[n].maxn[1]=a[n].minn[1]=y,ins(n);
else ans=inf,query(root,x,y),printf("%d
",ans);
}
return 0;
}
小结：KD-Tree挺好理解的，代码也短，只不过有时候不容易发现这是一个KD-Tree问题，需要将题目中的狗逼对象向我们容易处理的空间或平面对象转化。