【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

Sample Output

1
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;

}

巴特西

【BZOJ2648】SJY摆棋子 KDtree