bzoj2648&&2716 kd-tree模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    char ch=getchar();int f=0,x=1;
    while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();}
    return f*x;
}
int F,n,m,rt;
struct P
{
    int d[2],mx[2],mn[2],v,l,r;
    int & operator [](int x)
    {
        return d[x];
    }
    friend int dis(P x,P y)
    {
        return abs(x[1]-y[1])+abs(x[0]-y[0]);
    }
    friend bool operator < (P x,P y)
    {
        return x[F]<y[F];
    }
}p[500005];
const int inf=1000000000;
struct kdtree
{
    P t[1000005],T;int ans;
    void update(int k)
    {
        int l=t[k].l,r=t[k].r;
        for(int i=0;i<2;i++)
        {
            t[k].mn[i]=t[k].mx[i]=t[k][i];
            if(l)
            {
                t[k].mn[i]=min(t[k].mn[i],t[l].mn[i]);
                t[k].mx[i]=max(t[k].mx[i],t[l].mx[i]);
            }
            if(r)
            {
                t[k].mn[i]=min(t[k].mn[i],t[r].mn[i]);
                t[k].mx[i]=max(t[k].mx[i],t[r].mx[i]);
            }
        }   
    }
    int build(int l,int r,int now)
    {
        F=now;
        int mid=l+r>>1;
        nth_element(p+l,p+mid,p+r+1);
        t[mid]=p[mid];
        for(int i=0;i<2;i++) t[mid].mn[i]=t[mid].mx[i]=t[mid][i];
        if(l<mid) t[mid].l=build(l,mid-1,now^1);
        if(r>mid) t[mid].r=build(mid+1,r,now^1);
        update(mid);
        return mid;
    }
    void insert(int k,int now)
    {
        if(T[now]>=t[k][now])
        {
            if(t[k].r) insert(t[k].r,now^1);
            else
            {
                t[k].r=++n;t[n]=T;
                for(int i=0;i<2;i++)
                t[n].mn[i]=t[n].mx[i]=t[n][i];
            }
        }
        else
        {
            if(t[k].l) insert(t[k].l,now^1);
            else
            {
                t[k].l=++n;t[n]=T;
                for(int i=0;i<2;i++)
                t[n].mn[i]=t[n].mx[i]=t[n][i];
            }
        }
        update(k);
    }
    void insert(P p)
    {
        T=p;insert(rt,0);
    }
    int get(int k,P p)
    {
        int tmp=0;
        for(int i=0;i<2;i++) tmp+=max(0,t[k].mn[i]-p[i]);
        for(int i=0;i<2;i++) tmp+=max(p[i]-t[k].mx[i],0);
        return tmp;
    }
    void query(int k,int now)
    {
        int dl=inf,dr=inf,d;
        d=dis(t[k],T);
        ans=min(ans,d);
        if(t[k].l) dl=get(t[k].l,T);
        if(t[k].r) dr=get(t[k].r,T);
        if(dl<dr)
        {
            if(dl<ans) query(t[k].l,now^1);
            if(dr<ans) query(t[k].r,now^1);
        }
        else
        {
            if(dr<ans) query(t[k].r,now^1);
            if(dl<ans) query(t[k].l,now^1);
        }
    }
    int query(P p)
    {
        ans=inf;
        T=p;
        query(rt,0);
        return ans;
    }
}kd;
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    p[i][0]=read(),p[i][1]=read();
    rt=kd.build(1,n,0);
    while(m--)
    {
        int op=read(),x=read(),y=read();
        P tmp;
        tmp[0]=x;
        tmp[1]=y;
        if(op==1) kd.insert(tmp);
        else printf("%d\n",kd.query(tmp));
    }
}