似乎跟已有讨论比较像，但那一篇好像是序列根号分块（大概）

题解好像倍增分块都套了个线段树，那可不可以倍增分块套个 Splay，感觉简单分析下复杂度应该是相同的，问题是 Subtask4 TLE、MLE 了不少点，这个是因为常数太大还是复杂度不对，不知道再怎么优化了，还是说这个题不能这么写（我菜炸了）

如果需要的话代码放下面了，简单写了写注释，有没有大佬帮忙看下。

提交记录

#include <bits/stdc++.h>
#define lint long long
#define rint register int
using namespace std;
inline lint read(){
	char c;lint f=1,res=0;
	while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return res*f;
}
const int N=7e5+5,L=32,B=8;
const int inf=0x3f3f3f3f,md=1ll<<20;
lint lb[B],rb[B];
int rt[B];
//对应子树值域区间为[lb,rb]
inline void init(){
	lint pw=1;
	for(rint i=0;i<B;++i){
		lb[i]=pw;pw*=L;
		rb[i]=pw-1;
//		cout<<i<<" lb:"<<lb[i]<<" rb:"<<rb[i]<<endl;
	}
} 
//查找x所在的块 
inline int gbk(int x)
	{return upper_bound(lb+1,lb+B,x)-lb-1;}
int ch[N][2],fa[N],cnt[N],tot,rub[N],nr,p[N];
lint sum[N],ta[N];int w[N],mx[N],mn[N];
/*
sum子树和 w当前点的值 p当前点序列坐标
mx/mn子树最大/最小值 ta区间加标记 cnt子树大小  
*/
inline int np()
	{return nr?rub[nr--]:++tot;}
inline void clr(int x){
	fa[x]=ch[x][0]=ch[x][1]=0;
	cnt[x]=w[x]=sum[x]=0;
	mx[x]=0;mn[x]=inf;rub[++nr]=x;
}
inline void add(int x,lint v){
	if(!x)return;
	w[x]+=v;ta[x]+=v;mx[x]+=v;
	mn[x]+=v;sum[x]+=v*cnt[x];
}
inline void pushdown(int x){
	if(!ta[x])return;
	add(ch[x][0],ta[x]);
	add(ch[x][1],ta[x]);
	ta[x]=0;
}
inline void calc(int x){
	int lc=ch[x][0],rc=ch[x][1];
	sum[x]=sum[lc]+sum[rc]+w[x];
	cnt[x]=1+cnt[lc]+cnt[rc];
	mx[x]=max(w[x],max(mx[lc],mx[rc]));
	mn[x]=min(w[x],min(lc?mn[lc]:inf,rc?mn[rc]:inf));
}
inline void con(int r,int x,int y,int d){
	if(!y)rt[r]=x;
	else ch[y][d]=x,calc(y);
	if(x)fa[x]=y;
}
inline int d(int x)
	{return x==ch[fa[x]][1];}
inline void rot(int r,int x){
	int y=fa[x],z=fa[y];
	int dx=d(x),dy=d(y),w=ch[x][dx^1];
	con(r,x,z,dy);con(r,w,y,dx);con(r,y,x,dx^1);
}
void pushall(int x){
	if(!x)return;
	pushall(fa[x]);
	pushdown(x);
}
inline void splay(int r,int x,int tar){
	pushall(x);
	while(fa[x]!=tar){
		int y=fa[x],z=fa[y];
		int dx=d(x),dy=d(y);
		if(z&&z!=tar)
			rot(r,dx==dy?y:x);
		rot(r,x);
	}
}
//r子树中 找到x 是y的d儿子 插入pos位置的val值 
void inst(int r,int x,int y,int d,int pos,lint val){
	if(!x){
		x=np();p[x]=pos;w[x]=val;
		calc(x);con(r,x,y,d);
		splay(r,x,0);return;
	}pushdown(x);
	if(pos<=p[x])
		inst(r,ch[x][0],x,0,pos,val);
	else
		inst(r,ch[x][1],x,1,pos,val);
}
//查找p<=pos的点数 
int pcnt(int r,int x,int y,int pos){
	if(!x){splay(r,y,0);return 0;}
	pushdown(x);int lc=ch[x][0],rc=ch[x][1];
	if(p[x]>pos)return pcnt(r,lc,x,pos);
	else return pcnt(r,rc,x,pos)+cnt[lc]+1;
}
//找到第k大并返回节点编号 
int find(int r,int x,int k){
	if(!x)return 0;
	pushdown(x);int lc=ch[x][0],rc=ch[x][1];
	if(k==cnt[lc]+1){splay(r,x,0);return x;}
	else if(k<=cnt[lc])return find(r,lc,k);
	else return find(r,rc,k-cnt[lc]-1);
}
//截取区间并返回对应子树根节点 
inline int split(int r,int lp,int rp){
	int p0=find(r,rt[r],pcnt(r,rt[r],0,lp-1));
	int p1=find(r,rt[r],pcnt(r,rt[r],0,rp)+1);
	if(p0&&p1){splay(r,p0,0),splay(r,p1,p0);return ch[p1][0];}
	else if(p0){splay(r,p0,0);return ch[p0][1];}
	else if(p1){splay(r,p1,0);return ch[p1][0];}
	else return rt[r];
}
void print(int x){
	if(!x)return;
	cout<<x<<" fa:"<<fa[x]<<" lrc:"<<ch[x][0]<<" "<<ch[x][1]<<endl;
	cout<<"w:"<<w[x]<<" p:"<<p[x]<<" sum:"<<sum[x]<<" cnt:"<<cnt[x]<<" mxn:"<<mx[x]<<" "<<mn[x]<<endl;
	print(ch[x][0]);print(ch[x][1]);
}
int st[N],tp;//用于储存需要挪动的点标号
//不可以改变树的结构  
//对能直接区间减的区间减 能单点减的单点减
//把那些单点减完不在范围内的压进栈 
void sub(int r,int x,lint val){
	if(!x)return;
	if(mn[x]-val>=lb[r])
		{add(x,-val);return;}
	if(mx[x]<=val)return;
	pushdown(x);
	sub(r,ch[x][0],val);
	sub(r,ch[x][1],val);
	calc(x);
	if(w[x]<=val)return;
	w[x]-=val;calc(x);
	if(w[x]<lb[r])st[++tp]=x;
}
inline void upd(lint sv,int lp,int rp){
	for(rint i=0;i<B;++i){
		if(sv>rb[i])continue;
		int r=split(i,lp,rp);
		sub(i,r,sv);
		while(tp){
			int x=st[tp--];splay(i,x,0);
			int pos=p[x];lint val=w[x];
			if(ch[x][0]){
				int y=ch[x][0];
				while(ch[y][1])y=ch[y][1];
				splay(i,y,x);//找到x的前驱翻上来
				con(i,ch[x][1],y,1);
				con(i,y,0,0);
			}else con(i,ch[x][1],0,0);
			clr(x);
			r=gbk(val);
			inst(r,rt[r],0,0,pos,val); 
		}
	}
}
int n,m;lint lst=0;
int main(){
	n=read();m=read();
//	freopen("debug.txt","w",stdout);
	init();
	for(rint i=1;i<=n;++i){
		lint x=read();int r=gbk(x);
		inst(r,rt[r],0,0,i,x);
	}
	while(m--){
		int op=read();
		int lp=read()^lst,rp=read()^lst;
		if(op==1){
			lint x=read()^lst;
			upd(x,lp,rp);
		}else if(op==2){
			int amx=0,amn=inf;lint as=0;
			for(rint i=0;i<B;++i){
				int r=split(i,lp,rp);
				if(!r)continue;
				amx=max(amx,mx[r]);
				amn=min(amn,mn[r]);
				as+=sum[r];
			}
			printf("%lld %d %d\n",as,amn,amx);
			lst=as%md;
		}
	}
	return 0;
}