刚学OI萌新求调KD树

RT

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define lc tr[u].ls
#define rc tr[u].rs
using namespace std;

const int N=5e5+10;
const double alpha=0.7;
struct point{
    int dim[2],val;
    point(){};
    point(int x,int y,int vall){
        dim[0]=x;
        dim[1]=y;
        val=vall;
    }
}order[N];
int cnt,tot,root,top,trst[N],now;
struct kd_tree{
    int ls,rs,mi[2],ma[2],sum,size;
    point p;
}tr[N];

bool cmp(point a,point b){
    return a.dim[now]<b.dim[now];
}

void update(int u){
    for(int i=0;i<2;++i){
        tr[u].mi[i]=tr[u].ma[i]=tr[u].p.dim[i];
        if(lc){
            tr[u].mi[i]=min(tr[u].mi[i],tr[lc].mi[i]);
            tr[u].ma[i]=max(tr[u].ma[i],tr[lc].ma[i]);
        }
        if(rc){
            tr[u].mi[i]=min(tr[u].mi[i],tr[rc].mi[i]);
            tr[u].ma[i]=max(tr[u].ma[i],tr[rc].ma[i]);
        }
    }
    tr[u].sum=tr[lc].sum+tr[rc].sum+tr[u].p.val;
    tr[u].size=tr[lc].size+tr[rc].size+1;
}

void slap(int u){
    if(!u){
        return;
    }
    slap(lc);
    order[++cnt]=tr[u].p;
    trst[++top]=u;
    slap(rc);
}

int build(int l,int r,int d){
    if(l>r){
        return 0;
    }
    int u;
    if(top){
        u=trst[top--];
    }else{
        u=++tot;
    }
    int mid=l+r>>1;
    now=d;
    nth_element(order+1,order+mid,order+r+1,cmp);
    tr[u].p=order[mid];
    lc=build(l,mid-1,d^1);
    rc=build(mid+1,r,d^1);
    update(u);
    return u;
}

bool notbalance(int u){
    if(tr[lc].size>alpha*tr[u].size||tr[rc].size>alpha*tr[u].size){
        return true;
    }
    return false;
}

void insert(int &u,point now,int d){
    if(!u){
        if(top){
            u=trst[top--];
        }else{
            u=++tot;
        }
        lc=rc=0;
        tr[u].p=now;
        update(u);
        return;
    }
    if(now.dim[d]<=tr[u].p.dim[d]){
        insert(lc,now,d^1);
    }else{
        insert(rc,now,d^1);
    }
    update(u);
    if(notbalance(u)){
        cnt=0;
        slap(u);
        u=build(1,tr[u].size,d);
    }
}

int query(int u,int x1,int y1,int x2,int y2){
    if(!u){
        return 0;
    }
    int X1=tr[u].mi[0],Y1=tr[u].mi[1],X2=tr[u].ma[0],Y2=tr[u].ma[1];
    if(x1<=X1&&x2>=X2&&y1<=Y1&&y2>=Y2){
        return tr[u].sum;
    }
    if(x1>X2||x2<X1||y1>Y2||y2<Y1){
        return 0;
    }
    int ans=0;
    X1=X2=tr[u].p.dim[0],Y1=Y2=tr[u].p.dim[1];
    if(x1<=X1&&x2>=X2&&y1<=Y1&&y2>=Y2){
        ans+=tr[u].p.val;
    }
    ans+=query(lc,x1,y1,x2,y2)+query(rc,x1,y1,x2,y2);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    int ans=0;
    while(1){
        int opt;
        cin>>opt;
        if(opt==1){
            int x,y,val;
            cin>>x>>y>>val;
            x^=ans;
            y^=ans;
            val^=ans;
            insert(root,point(x,y,val),0);
        }else if(opt==2){
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            x1^=ans;
            y1^=ans;
            x2^=ans;
            y2^=ans;
            ans=query(root,x1,y1,x2,y2);
            cout<<ans<<endl;
        }else{
            break;
        }
    }
    return 0;
}