bzoj2648 SJY摆棋子【KD-tree模板】

解题思路：

KD-tree是一种维护多维空间中点的数据结构。
讲解详见http://blog.csdn.net/jiangshibiao/article/details/34144829。
本题中的操作都有涉及。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int getint()
{
int i=0,f=1;char c;
for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
return i*f;
}

const int N=1000005,INF=0x3f3f3f3f;
struct node
{
int min[2],max[2],d[2],l,r;
}tr[N];
int n,m,D,root,ans,op,x,y;

inline bool cmp(const node &a,const node &b)
{
if(a.d[D]==b.d[D])return a.d[D^1]<b.d[D^1];
return a.d[D]<b.d[D];
}

inline void update(int k,int s)
{
tr[k].min[0]=min(tr[k].min[0],tr[s].min[0]);
tr[k].min[1]=min(tr[k].min[1],tr[s].min[1]);
tr[k].max[0]=max(tr[k].max[0],tr[s].max[0]);
tr[k].max[1]=max(tr[k].max[1],tr[s].max[1]);
}

int build(int l,int r,int dd)
{
int mid=l+r>>1;
    D=dd;
    nth_element(tr+l+1,tr+mid+1,tr+r+1,cmp);
tr[mid].max[0]=tr[mid].min[0]=tr[mid].d[0];
tr[mid].max[1]=tr[mid].min[1]=tr[mid].d[1];
if(l!=mid)tr[mid].l=build(l,mid-1,dd^1);
if(r!=mid)tr[mid].r=build(mid+1,r,dd^1);
if(tr[mid].l)update(mid,tr[mid].l);
if(tr[mid].r)update(mid,tr[mid].r);
return mid;
}

inline void Insert(int k)
{
int p=root;D=0;
while(1)
    {
        update(p,k);
if(tr[k].d[D]<=tr[p].d[D])
        {
if(!tr[p].l){tr[p].l=k;return;}
            p=tr[p].l;
        }
else
        {
if(!tr[p].r){tr[p].r=k;return;}
            p=tr[p].r;
        }
        D^=1;
    }
}

inline int getdis(int k)
{
int res=0;
if(x<tr[k].min[0])res+=tr[k].min[0]-x;
if(x>tr[k].max[0])res+=x-tr[k].max[0];
if(y<tr[k].min[1])res+=tr[k].min[1]-y;
if(y>tr[k].max[1])res+=y-tr[k].max[1];
return res;
}

void query(int k)
{
int d=abs(tr[k].d[0]-x)+abs(tr[k].d[1]-y);
    ans=min(ans,d);
int dl=(tr[k].l?getdis(tr[k].l):INF);
int dr=(tr[k].r?getdis(tr[k].r):INF);
if(dl<=dr)
    {
if(dl<ans)query(tr[k].l);
if(dr<ans)query(tr[k].r);
    }
else
    {
if(dr<ans)query(tr[k].r);
if(dl<ans)query(tr[k].l);
    }
}

int main()
{
//freopen("lx.in","r",stdin);
    n=getint(),m=getint();
for(int i=1;i<=n;i++)
tr[i].d[0]=getint(),tr[i].d[1]=getint();
    root=build(1,n,0);
while(m--)
    {
        op=getint(),x=getint(),y=getint();
if(op==1)
        {
            ++n;
tr[n].max[0]=tr[n].min[0]=tr[n].d[0]=x;
tr[n].max[1]=tr[n].min[1]=tr[n].d[1]=y;
            Insert(n);
        }
else 
        {
            ans=INF;
            query(root);
            cout<<ans<<'\n';
        }
    }
return 0;
}