相信信仰剪枝的力量

namespace kdtree
{
    int cmp_id,root;
    struct inf
    {
        int lc,rc,p,min[2],max[2],x[2];
        int ind;
        bool able;
    }t[NN];
    bool operator < (const inf& t1,const inf& t2)
    {if(t1.x[cmp_id]==t2.x[cmp_id])return t1.x[1^cmp_id]<t2.x[1^cmp_id];
    return t1.x[cmp_id]<t2.x[cmp_id];}
    int tot;
    void addpoint(int ind,int px,int py,bool able)
    {++tot;t[tot].ind=ind;t[tot].x[0]=px;t[tot].x[1]=py;t[tot].able=able;}
    void updata(int o)
    {
        if(!t[o].able)
        {t[o].min[0]=t[o].min[1]=INF;t[o].max[0]=t[o].max[1]=-INF;}
        else
        {t[o].min[0]=t[o].max[0]=t[o].x[0];t[o].min[1]=t[o].max[1]=t[o].x[1];}
        if(t[o].lc)
        {
            int lc=t[o].lc;
            if(t[lc].min[0]<t[o].min[0])t[o].min[0]=t[lc].min[0];
            if(t[lc].max[0]>t[o].max[0])t[o].max[0]=t[lc].max[0];
            if(t[lc].min[1]<t[o].min[1])t[o].min[1]=t[lc].min[1];
            if(t[lc].max[1]>t[o].max[1])t[o].max[1]=t[lc].max[1];
        }
        if(t[o].rc)
        {
            int rc=t[o].rc;
            if(t[rc].min[0]<t[o].min[0])t[o].min[0]=t[rc].min[0];
            if(t[rc].max[0]>t[o].max[0])t[o].max[0]=t[rc].max[0];
            if(t[rc].min[1]<t[o].min[1])t[o].min[1]=t[rc].min[1];
            if(t[rc].max[1]>t[o].max[1])t[o].max[1]=t[rc].max[1];
        }
    }
    int build(int l,int r,int p,int d)
    {
        int mid=(l+r)>>1;cmp_id=d;
        nth_element(t+l,t+mid,t+r+1);
        t[mid].p=p;
        if(l<mid)t[mid].lc=build(l,mid-1,mid,1^d);
        if(mid<r)t[mid].rc=build(mid+1,r,mid,1^d);
        updata(mid);
        return mid;
    }
    void build()
    {
        root=build(1,tot,0,0);
        for(int i=1;i<=tot;i++)pos[t[i].ind]=i;
    }
    inline int dist_upper(int o,int px,int py)
    {
        if(t[o].max[0]==-INF)return INF;
        int dist=0;
        if(t[o].max[0]<px)dist+=px-t[o].max[0];
        if(t[o].min[0]>px)dist+=t[o].min[0]-px;
        if(t[o].max[1]<py)dist+=py-t[o].max[1];
        if(t[o].min[1]>py)dist+=t[o].min[1]-py;
        return dist;
    }
    inline int dist(int o,int px,int py)
    {if(!t[o].able)return INF;
    return abs(t[o].x[0]-px)+abs(t[o].x[1]-py);}
    int ans;
    inline void query(int o,int px,int py)
    {
        int dl=INF,dr=INF,d0=dist(o,px,py);
        if(d0<ans)ans=d0;
        if(t[o].lc)dl=dist_upper(t[o].lc,px,py);
        if(t[o].rc)dr=dist_upper(t[o].rc,px,py);
        if(dl<dr)
        {
            if(dl<ans)query(t[o].lc,px,py);
            if(dr<ans)query(t[o].rc,px,py);
        }
        else
        {
            if(dr<ans)query(t[o].rc,px,py);
            if(dl<ans)query(t[o].lc,px,py);
        }
    }
    int query(int px,int py)
    {
        ans=INF-1;query(root,px,py);
        return ans;
    }
    void execute(int o)
    {
        o=pos[o];t[o].able=true;
        while(o)
        {
            updata(o);
            o=t[o].p;
        }
    }
    void show(int o)
    {
        if(t[o].lc)show(t[o].lc);
        printf("(%d,%d)\n",t[o].x[0],t[o].x[1]);
        if(t[o].rc)show(t[o].rc);
    }
    void show(){show(root);}
}

upd@2012.1.3：模板居然是错的。摆棋子那道题的数据得是有多弱。

nth_element(t+l+1,t+mid+1,t+r+1);

↓

nth_element(t+l,t+mid,t+r+1);

突然想起来很久以后的一道题，回去翻了翻别人的代码发现kdt有一种奇怪的用法。在2dtree中，记能包住每个点的子树中所有点的最小矩形。要查询在某条直线以下的所有点的权值和的时候，判断这棵子树是不是都在直线以下/以上/穿过。第一第二种情况都可以直接return，第三种情况递归。

完全不懂复杂度。