【悬关】KDT 模板 50pts Sub2,4 全 WA 求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
const double alpha=0.75;
int K,Q,n,rt,tot,lst,a[N],now;
struct kdt{
    int ls,rs,siz,sum;
    int x[3],v,dim,tg;
    int mx[3],mn[3];
    #define ls(x) tr[x].ls
	#define rs(x) tr[x].rs
	#define siz(x) tr[x].siz
	#define sum(x) tr[x].sum
	#define dim(x) tr[x].dim
    #define tg(x) tr[x].tg
}tr[N];
void chkmin(int &x,int y){if(x>y)x=y;return;}
void chkmax(int &x,int y){if(x<y)x=y;return;}
void ps(int cur){
	siz(cur)=siz(ls(cur))+siz(rs(cur))+1;
	sum(cur)=sum(ls(cur))+sum(rs(cur))+tr[cur].v;
	for(int i=0;i<K;i++){
        tr[cur].mx[i]=tr[cur].mn[i]=tr[cur].x[i];
        if(ls(cur))
            chkmax(tr[cur].mx[i],tr[ls(cur)].mx[i]),
            chkmin(tr[cur].mn[i],tr[ls(cur)].mn[i]);
        if(rs(cur))
            chkmax(tr[cur].mx[i],tr[rs(cur)].mx[i]),
            chkmin(tr[cur].mn[i],tr[rs(cur)].mn[i]);
	}
	return;
}
bool chk(int cur){
    if(max(siz(ls(cur)),siz(rs(cur)))>=1.0*alpha*siz(cur))return 1;
	return 0;
}
bool cmp(int x,int y){return tr[x].x[now]<tr[y].x[now];}
void bd(int &cur,int l,int r,int k){
	if(l>r)return cur=0,void();
	int mid=l+r>>1;
	now=k,nth_element(a+l,a+mid,a+r+1,cmp);
	cur=a[mid],dim(cur)=k;
	bd(ls(cur),l,mid-1,(k+1)%K),bd(rs(cur),mid+1,r,(k+1)%K),ps(cur);
	return;
}
void ad(int cur,int val){tg(cur)+=val,sum(cur)+=val*siz(cur),tr[cur].v+=val;}
void alpd(int cur){
    if(!cur||!tg(cur))return;
    if(ls(cur))ad(ls(cur),tg(cur));
    if(rs(cur))ad(rs(cur),tg(cur));
    tg(cur)=0;
    if(ls(cur))alpd(ls(cur));
    if(rs(cur))alpd(rs(cur));
    return;
}
void ret(int cur){if(!cur)return;ret(ls(cur)),a[++n]=cur,ret(rs(cur));}
void rebd(int &cur){n=0,alpd(cur),ret(cur),bd(cur,1,n,0);}
void ins(int &cur,int x){
	if(!cur)return cur=x,ps(cur),void();
	if(tr[x].x[dim(cur)]<=tr[cur].x[dim(cur)])ins(ls(cur),x);
	else ins(rs(cur),x);
	ps(cur);
	if(chk(cur))rebd(cur);
	return;
}
void pd(int cur){
    if(!tg(cur))return;
    if(ls(cur))ad(ls(cur),tg(cur));
    if(rs(cur))ad(rs(cur),tg(cur));
    return tg(cur)=0,void();
}
int qyk2(int cur,int l1,int r1,int l2,int r2){
    if(!cur||r1<tr[cur].mn[0]||l1>tr[cur].mx[0]||r2<tr[cur].mn[1]||l2>tr[cur].mx[1])return 0;
    if(l1<=tr[cur].mn[0]&&tr[cur].mx[0]<=r1&&l2<=tr[cur].mn[1]&&tr[cur].mx[1]<=r2)return sum(cur);
    int res=0;
    if(l1<=tr[cur].x[0]&&tr[cur].x[0]<=r1&&l2<=tr[cur].x[1]&&tr[cur].x[1]<=r2)res=tr[cur].v;
    return pd(cur),res+qyk2(ls(cur),l1,r1,l2,r2)+qyk2(rs(cur),l1,r1,l2,r2);
}
void updk2(int cur,int l1,int r1,int l2,int r2,int val){
    if(!cur||r1<tr[cur].mn[0]||l1>tr[cur].mx[0]||r2<tr[cur].mn[1]||l2>tr[cur].mx[1])return;
    if(l1<=tr[cur].mn[0]&&tr[cur].mx[0]<=r1&&l2<=tr[cur].mn[1]&&tr[cur].mx[1]<=r2)
        return ad(cur,val),void();
    if(l1<=tr[cur].x[0]&&tr[cur].x[0]<=r1&&l2<=tr[cur].x[1]&&tr[cur].x[1]<=r2)tr[cur].v+=val;
    pd(cur),updk2(ls(cur),l1,r1,l2,r2,val),updk2(rs(cur),l1,r1,l2,r2,val),ps(cur);
    return;
}
int qyk3(int cur,int l1,int r1,int l2,int r2,int l3,int r3){
    if(!cur||r1<tr[cur].mn[0]||l1>tr[cur].mx[0]||r2<tr[cur].mn[1]||l2>tr[cur].mx[1]||r3<tr[cur].mn[2]||l3>tr[cur].mx[2])return 0;
    if(l1<=tr[cur].mn[0]&&tr[cur].mx[0]<=r1&&l2<=tr[cur].mn[1]&&tr[cur].mx[1]<=r2&&l3<=tr[cur].mn[2]&&tr[cur].mx[2]<=r3)return sum(cur);
    int res=0;
    if(l1<=tr[cur].x[0]&&tr[cur].x[0]<=r1&&l2<=tr[cur].x[1]&&tr[cur].x[1]<=r2&&l3<=tr[cur].x[2]&&tr[cur].x[2]<=r3)res=tr[cur].v;
    return pd(cur),res+qyk3(ls(cur),l1,r1,l2,r2,l3,r3)+qyk3(rs(cur),l1,r1,l2,r2,l3,r3);
}
void updk3(int cur,int l1,int r1,int l2,int r2,int l3,int r3,int val){
    if(!cur||r1<tr[cur].mn[0]||l1>tr[cur].mx[0]||r2<tr[cur].mn[1]||l2>tr[cur].mx[1]||r3<tr[cur].mn[2]||l3>tr[cur].mx[2])return;
    if(l1<=tr[cur].mn[0]&&tr[cur].mx[0]<=r1&&l2<=tr[cur].mn[1]&&tr[cur].mx[1]<=r2&&l3<=tr[cur].mn[2]&&tr[cur].mx[2]<=r3)
        return ad(cur,val),void();
    if(l1<=tr[cur].x[0]&&tr[cur].x[0]<=r1&&l2<=tr[cur].x[1]&&tr[cur].x[1]<=r2&&l3<=tr[cur].x[2]&&tr[cur].x[2]<=r3)tr[cur].v+=val;
    pd(cur),updk3(ls(cur),l1,r1,l2,r2,l3,r3,val),updk3(rs(cur),l1,r1,l2,r2,l3,r3,val),ps(cur);
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>K>>Q;
    while(Q--){
        int op;cin>>op;
        if(op==1){
            int v;tot++;
            for(int i=1,x;i<=K;i++)cin>>x,x^=lst,tr[tot].x[i-1]=x;
            cin>>v,v^=lst,tr[tot].v=v,ins(rt,tot);
        }
        else if(op==2){
            int b[3],c[3],v;
            for(int i=0;i<K;i++)cin>>b[i],b[i]^=lst;
            for(int i=0;i<K;i++)cin>>c[i],c[i]^=lst;
            cin>>v,v^=lst;
            if(K==2)updk2(rt,b[0],c[0],b[1],c[1],v);
            else updk3(rt,b[0],c[0],b[1],c[1],b[2],c[2],v);
        }
        else{
            int b[3],c[3];
            for(int i=0;i<K;i++)cin>>b[i],b[i]^=lst;
            for(int i=0;i<K;i++)cin>>c[i],c[i]^=lst;
            if(K==2)lst=qyk2(rt,b[0],c[0],b[1],c[1]),cout<<lst<<"\n";
            else lst=qyk3(rt,b[0],c[0],b[1],c[1],b[2],c[2]),cout<<lst<<"\n";
        }
    }
    return 0;
}