线段树做法 RE 20pts求调

#include <bits/stdc++.h>
using namespace std;
namespace MySpace{
    #define lowbit(x) (x&(-x))
    #define sqrt sqrtl
    #ifdef ONLINE_JUDGE
    #define getchar getchar_unlocked
    #endif
    #define whileu(p) while (p--)
    #define forl(a,b,c) for (auto a=b;a<=c;a=a+1)
    inline void read() {}
    template <typename T, typename... R>
    inline void read(T &x,R &... oth){
        x=0;T f=1;
        char c=getchar();
        while(c<'0' || c>'9') {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c&15),c=getchar();
        x*=f;
        read(oth...);
        return;
    }
    template<typename T>
    T qpow(T a,T n,T p){
        T res=1;a%=p;
        while (n){
            if (n&1) res=1ll*res*a%p;
            a=1ll*a*a%p;
            n>>=1;
        }
        return res;
    }
    template<typename T>
    T gcd(T a,T b){return (b>0?gcd(b,a%b):a);}
    template<typename T>
    T exgcd(T a,T b,T& x,T& y){
        if (b<=0ll){
            x=1ll,y=0ll;
            return a;
        }
        T d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return d;
    }
    template<typename T>
    T inv(T a,T p){
        if (a==1) return 1ll;
        T x,y;
        if (exgcd(a,p,x,y)!=1ll) return -1ll;
        else return (x+p)%p;
    }
}
using namespace MySpace;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using ull=unsigned long long;
const int maxn=5e5+1145;
int n,q;
ull a[maxn];
ull tr[1<<20];
ull m[1<<20],mc[1<<20];//最小值和最小值计数 
ull cm[1<<20];//最小值计数
ull tag[1<<20],tagn[1<<20];//全局区间减 非min区间减 
void pushup(int x){
	tr[x]=tr[ls(x)]+tr[rs(x)];
	m[x]=m[ls(x)];mc[x]=mc[ls(x)];
	if (m[ls(x)]==m[rs(x)]){
		mc[x]+=mc[rs(x)];
		if (!(cm[x]=min(cm[ls(x)],cm[rs(x)]))) cm[x]=cm[ls(x)]|cm[rs(x)];
	}else if (!(cm[x]=min(cm[ls(x)],m[rs(x)]))){cm[x]=cm[ls(x)]|m[rs(x)];}
	return;
}
void allsub(int x,ull v,int l,int r){
	m[x]-=v;
	tag[x]+=v;
	tr[x]-=(r-l+1)*v;
	if (cm[x]) cm[x]-=v;
	return;
}
void nmsub(int x,ull v,int l,int r){
	tagn[x]+=v;
	tr[x]-=(r-l+1-mc[x])*v;
	if (cm[x]) cm[x]-=v;
	return;
}
void chosub(int x,ull v,ull minn,int l,int r){
	(m[x]==minn?nmsub:allsub)(x,v,l,r);
	return;
}
void pushdown(int x,int l,int r){
	int mid=(l+r)>>1;
	if (tag[x]){
		allsub(ls(x),tag[x],l,mid);
		allsub(rs(x),tag[x],mid+1,r);
		tag[x]=0; 
	}
	if (tagn[x]){
		chosub(ls(x),tagn[x],m[x],l,mid);
		chosub(rs(x),tagn[x],m[x],mid+1,r);
		tagn[x]=0; 
	}
	return; 
}
void update(int ql,int qr,ull v,int x=1,int l=1,int r=n){
	if (ql<=l && r<=qr){
		if (!cm[x] || m[x]>v){
			if (m[x]!=v) allsub(x,v,l,r);
			return;
		}
		if (m[x]==v && cm[x]>2*v){
			nmsub(x,v,l,r);
			return;
		}
	}
	int mid=(l+r)>>1;
	pushdown(x,l,r);
	if (ql<=mid) update(ql,qr,v,ls(x),l,mid);
	if (qr>=mid+1) update(ql,qr,v,rs(x),mid+1,r);
	pushup(x);
	return;
}
ull query(int ql,int qr,int x=1,int l=1,int r=n){
	if (ql<=l && r<=qr) return tr[x];
	int mid=(l+r)>>1;
	pushdown(x,l,r);
	ull res=0;
	if (ql<=mid) res+=query(ql,qr,ls(x),l,mid);
	if (qr>=mid+1) res+=query(ql,qr,rs(x),mid+1,r);
	pushup(x);
	return res;
}
void build(int x=1,int l=1,int r=n){
	if (l==r){
		tr[x]=m[x]=a[l];
		mc[x]=1;cm[x]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	pushup(x);
	return;
}
signed main(){
	read(n,q);
	for (int i=1;i<=n;i++) read(a[i]);
	build();
	ull lastans=0;
	while (q--){
		int opt,l,r,x;read(opt,l,r);
		l^=lastans,r^=lastans;
		if (opt==1){
			read(x);x^=lastans;
			update(l,r,x);
		}else{
			lastans=query(l,r);
			cout << lastans << '\n';
			lastans&=0xfffff;
		}
	}



	return 0;
}