K-D Tree 0pts 求条

/* ChongYun */
#include<bits/stdc++.h>
#define File(s,t) freopen(s".in","r",stdin),freopen(t".out","w",stdout)
#define Time() cerr<<fixed<<setprecision(6)<<1.*(double)(clock()-__st)/CLOCKS_PER_SEC<<"s\n"
#define Memory() cerr<<fixed<<setprecision(6)<<1.*fabs(&__t-&__s)/1024./1024.<<"MB\n"
char __s; clock_t __st;

#define break ({break;})
#define continue ({continue;})

#define int long long
#define ldb long double
#define ull unsigned long long
#define reg register

using namespace std;

#define pii pair<int,int>
#define fir first
#define sec second

#define flush() fwrite(obuf,1,O-obuf,stdout)
#define putchar(x) ((O==obuf+(1<<21))&&(flush(),O=obuf)),*O++=x
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define chLimit(x) (x>='a'&&x<='z')
inline char gc(){ reg char ch=getchar();while(!chLimit(ch)) ch=getchar();return ch; }

inline int read(){
	reg int x=0,f=1;
	reg char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar(); }
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x*f;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar((x%10)^48);
}
inline void write(int x,char ch){ write(x),putchar(ch); }
inline void write(string s){  for(reg int i=0;i<(int)s.size();++i) putchar(s[i]); }
struct Flush{ ~Flush(){ flush(); } }_;
const int N=1e6+5,B=21,inf=1e18;
int k,n,q,ans,a[N],rt[B],tot;
struct KDTree{ int ls,rs,siz,sum,val,tag,x[3],lt[3],rt[3]; }T[N],L,R;
#define ls(p) T[p].ls
#define rs(p) T[p].rs
void pushup(int p){
    T[p].siz=T[ls(p)].siz+T[rs(p)].siz+1;
    T[p].sum=T[ls(p)].sum+T[rs(p)].sum+T[p].val;
    for(int i=0;i<k;++i){
        T[p].lt[i]=min({T[p].x[i],T[ls(p)].lt[i],T[rs(p)].lt[i]});
        T[p].rt[i]=max({T[p].x[i],T[ls(p)].rt[i],T[rs(p)].rt[i]});
    }
}
void addtag(int p,int x){ T[p].tag+=x,T[p].val+=x,T[p].sum+=x*T[p].siz; }
void pushdown(int p){
    if(T[p].tag){
        if(ls(p)) addtag(ls(p),T[p].tag);
        if(rs(p)) addtag(rs(p),T[p].tag);
        T[p].tag=0;
    }
}
int build(int l,int r,int t=0){
    if(l>r) return 0;
    int mid=(l+r)>>1;
    nth_element(a+l,a+mid,a+r+1,[t](int x,int y){ return T[x].x[t]<T[y].x[t]; });
    ls(a[mid])=build(l,mid-1,(t+1)%k);
    rs(a[mid])=build(mid+1,r,(t+1)%k);
    return pushup(a[mid]),a[mid];
}
void re(int &p){
    if(!p) return ;
    a[++n]=p;
    pushdown(p);
    re(ls(p)),re(rs(p));
    p=0;
}
bool IN(int *l,int *r){ for(int i=0;i<k;++i){ if(L.x[i]>l[i]||r[i]>R.x[i]) return 0; } return 1;  }
bool OUT(int *l,int *r){ for(int i=0;i<k;++i){ if((L.x[i]<=l[i]&&l[i]<=R.x[i])||(L.x[i]<=r[i]&&r[i]<=R.x[i])) return 0; } return 1; }
int query(int p){
    if(!p||OUT(T[p].lt,T[p].rt)) return 0;
    if(IN(T[p].lt,T[p].rt)) return T[p].sum;
    pushdown(p);
    return (IN(T[p].x,T[p].x)?T[p].val:0)+query(ls(p))+query(rs(p));
}
void upd(int p,int x){
    if(!p||OUT(T[p].lt,T[p].rt)) return ;
    if(IN(T[p].lt,T[p].rt)) return addtag(p,x);
    if(IN(T[p].x,T[p].x)) T[p].val+=x;
    pushdown(p);
    upd(ls(p),x),upd(rs(p),x);
    pushup(p);
}
#undef ls(p)
#undef rs(p)
namespace Tracy{
    void Main(){
        k=read(),q=read();
        T[0].lt[0]=T[0].lt[1]=T[0].lt[2]=inf;
        while(q--){
            int op=read();
            if(op==1){
                a[n=1]=++tot;
                for(int i=0;i<k;++i) T[tot].x[i]=read()^ans;
                T[tot].val=read()^ans;
                for(int i=0;i<B;++i){
                    if(rt[i]) re(rt[i]);
                    else{
                        rt[i]=build(1,n);
                        break;
                    }
                }
            }
            if(op==2){
                for(int i=0;i<k;++i) L.x[i]=read()^ans;
                for(int i=0;i<k;++i) R.x[i]=read()^ans;
                int x=read()^ans;
                for(int i=0;i<B;++i) upd(rt[i],x);
            }
            if(op==3){
                for(int i=0;i<k;++i) L.x[i]=read()^ans;
                for(int i=0;i<k;++i) R.x[i]=read()^ans;
                int res=0;
                for(int i=0;i<B;++i) res+=query(rt[i]);
                write(ans=res,'\n');
            }
        }
    }
	char __t;
    int Reznik(int T=1){
        __st=clock();
	    while(T--) Main();
	    return /*Time(),Memory(),*/0;
    }
}

signed main(){ 
	// File("","");
	return Tracy::Reznik(); 
}