BZOJ 4066 简单题（KD树）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4066

【题目大意】

　　要求维护矩阵内格子加点和矩阵查询

【题解】

　　往KD树上加权值点，支持矩阵查询即可，每隔5000个插入暴力重构树。

【代码】

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=300000,INF=1e9;

namespace KD_Tree{

    struct Dot{

        int d[2],mn[2],mx[2],l,r,sz,sum,val;

        Dot(){l=r=0;}

        Dot(int x,int y,int c){d[0]=x;d[1]=y;val=c;l=r=sz=sum=0;}

        int& operator [] (int x){return d[x];}

    };

    int D,dcnt=0,pt[N];

    Dot T[N];

    inline void umax(int&a,int b){if(a<b)a=b;}

    inline void umin(int&a,int b){if(a>b)a=b;}

    inline bool cmp(int x,int y){return T[x][D]<T[y][D];}

    inline void up(int x){

        T[x].sz=T[T[x].l].sz+T[T[x].r].sz+1;

        T[x].sum=T[T[x].l].sum+T[T[x].r].sum+T[x].val;

        T[x].mn[0]=T[x].mx[0]=T[x][0];

        T[x].mn[1]=T[x].mx[1]=T[x][1];

        if(T[x].l){

            umax(T[x].mx[0],T[T[x].l].mx[0]);

            umin(T[x].mn[0],T[T[x].l].mn[0]);

            umax(T[x].mx[1],T[T[x].l].mx[1]);

            umin(T[x].mn[1],T[T[x].l].mn[1]);

        }

        if(T[x].r){

            umax(T[x].mx[0],T[T[x].r].mx[0]);

            umin(T[x].mn[0],T[T[x].r].mn[0]);

            umax(T[x].mx[1],T[T[x].r].mx[1]);

            umin(T[x].mn[1],T[T[x].r].mn[1]);

        }

    }

    inline int NewDot(int x,int y,int c){

        ++dcnt; pt[dcnt]=dcnt;

        T[dcnt][0]=x; T[dcnt][1]=y; T[dcnt].val=c;

        return up(dcnt),dcnt;

    }

    // 查询矩阵内数字和

    int query(int x,int x0,int y0,int x1,int y1){

        if(!x||T[x].mn[0]>x1||T[x].mx[0]<x0||T[x].mn[1]>y1||T[x].mx[1]<y0)return 0;

        if(T[x].mn[0]>=x0&&T[x].mx[0]<=x1&&T[x].mn[1]>=y0&&T[x].mx[1]<=y1)return T[x].sum;

        int res=0;

        if(T[x][0]>=x0&&T[x][0]<=x1&&T[x][1]>=y0&&T[x][1]<=y1)res+=T[x].val;

        return res+query(T[x].l,x0,y0,x1,y1)+query(T[x].r,x0,y0,x1,y1);

    }

    void Insert(int&x,int D,const Dot&p){

        if(!x){x=NewDot(p.d[0],p.d[1],p.val);return;}

        if(p.d[D]<T[x][D])Insert(T[x].l,D^1,p);

        else Insert(T[x].r,D^1,p);

        up(x);

    }

    // 暴力重构

    int Rebuild(int l,int r,int now){

        if(l>r)return 0;

        int mid=(l+r)>>1,x;

        D=now;

        nth_element(pt+l,pt+mid,pt+r+1,cmp);

        x=pt[mid];

        T[x].l=Rebuild(l,mid-1,now^1);

        T[x].r=Rebuild(mid+1,r,now^1);

        return up(x),x;

    }

}

int n,op,x0,y0,x1,y1,c,ans=0,root=0;

int main(){

    scanf("%d",&n);

    while(scanf("%d",&op)){

        if(op==3)break;

        if(op==1){

            scanf("%d%d%d",&x0,&y0,&c);

            x0^=ans,y0^=ans,c^=ans;

            KD_Tree::Insert(root,0,KD_Tree::Dot(x0,y0,c));

            if(KD_Tree::dcnt%5000==0)root=KD_Tree::Rebuild(1,KD_Tree::dcnt,0);

        }else{

            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);

            x0^=ans,y0^=ans,x1^=ans,y1^=ans;

            printf("%d\n",ans=KD_Tree::query(root,x0,y0,x1,y1));

        }

    }return 0;

}