KDTRE20求助

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

int k=0;

class KDT
{
    int n;
    class point
    {
        public:
        int x,y,w,x_1,y_1,x_2,y_2,w_;
        point*son[2];
        bool operator<(const point a)const
        {
            if(k==1)return x<a.x;
            return y<a.y;
        }
    };
    point *root;
    vector<point>rebuild,a;
    public:
    point* build(point*l,point*r)
    {
        if(l==r)
        {
            return l;
        }
        point* mid=l+(r-l>>1);
        nth_element(l,mid,r);
        k^=1;
        if(l<=mid-1)mid->son[0]=build(l,mid-1);
        if(mid+1<=r)mid->son[1]=build(mid+1,r);
        k^=1;
        if(mid->son[0]!=NULL)mid->w_+=mid->son[0]->w_,mid->x_1=min(mid->son[0]->x_1,mid->x_1),mid->y_1=min(mid->son[0]->y_1,mid->y_1),mid->x_2=max(mid->son[0]->x_2,mid->x_2),mid->y_2=max(mid->son[0]->y_2,mid->y_2);
        if(mid->son[1]!=NULL)mid->w_+=mid->son[1]->w_,mid->x_1=min(mid->son[1]->x_1,mid->x_1),mid->y_1=min(mid->son[1]->y_1,mid->y_1),mid->x_2=max(mid->son[1]->x_2,mid->x_2),mid->y_2=max(mid->son[1]->y_2,mid->y_2);

        return mid;
    }
    void insert(int x,int y,int w)
    {
        root=NULL;
        rebuild.push_back({x,y,w,x,y,x,y,w,NULL,NULL});
        if(rebuild.size()>=sqrt(n))
        {
            for(auto i:rebuild)a.push_back(i);
            root=build(&a[0],&a[a.size()-1]);
            while(rebuild.size()!=0)rebuild.pop_back();
        }
    }
    int query_sum_(point*u,int x_1,int y_1,int x_2,int y_2)
    {
        if(u==NULL)return 0;
        if(x_1<=u->x_1&&x_2>=u->x_2&&y_1<=u->y_1&&y_2>=u->y_2)return u->w_;
        if(x_1>u->x_2||x_2<u->x_1||y_1>u->y_2||y_2<u->y_1)return 0;
        int ans=0;
        if(u->x<=x_2&&u->x>=x_1&&u->y<=y_2&&u->y>=y_1)ans+=u->w;
        if(u->son[0]!=NULL)ans+=query_sum_(u->son[0],x_1,y_1,x_2,y_2);
        if(u->son[1]!=NULL)ans+=query_sum_(u->son[1],x_1,y_1,x_2,y_2);
        return ans;
    }
    int query_sum(int x_1,int y_1,int x_2,int y_2)
    {
        int ans=0;
        for(int j=0;j<rebuild.size();j++)
        {
            point i=rebuild[j];
            if(i.x<=x_2&&i.x>=x_1&&i.y<=y_2&&i.y>=y_1)ans+=i.w;
        }
        return ans+query_sum_(root,x_1,y_1,x_2,y_2);
    }
};

int n,ans,Type;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    KDT t;
    cin>>n>>Type;
    while(Type!=3)
    {
        if(Type==1)
        {
            int x,y,w;
            cin>>x>>y>>w;
            x^=ans;
            y^=ans;
            w^=ans;
            t.insert(x,y,w);
        }
        else
        {
            int x_1,y_1,x_2,y_2;
            cin>>x_1>>y_1>>x_2>>y_2;
            x_1^=ans;
            y_1^=ans;
            x_2^=ans;
            y_2^=ans;
            ans=t.query_sum(x_1,y_1,x_2,y_2);
            cout<<ans<<"\n";
        }
        cin>>Type;
    }
}