写道数据结构练练手哈哈哈
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define il inline
#define rg register
#define vd void
#define sta static
#define pr pair<int,int>
typedef long long ll;
using namespace std;
il char gc(){
const int B=10000000;static char b[B+1],*p=b+B;
if(p==b+B)b[fread(b,1,B,stdin)]=0,p=b;
return *p?*p++:0;
}
il int gi(){
rg int x=0;rg bool flg=0;rg char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=gc();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=gc();
return flg?-x:x;
}
const int maxn=100001<<1;
int rt,ls[maxn],rs[maxn],ran[maxn],siz[maxn],n,m;
ll sum[maxn],w[maxn],tga[maxn],tgb[maxn],tgc[maxn];
bool tgd[maxn];
il vd Set(int&x,ll y){if(x)w[x]=y,sum[x]=siz[x]*y,tgd[x]=1,tgc[x]=y,tga[x]=tgb[x]=0;}
il vd Adda(int&x,ll y){if(x)w[x]+=y*(siz[ls[x]]+1),sum[x]+=y*(1+siz[x])*siz[x]/2,tga[x]+=y;}
il vd Addb(int&x,ll y){if(x)w[x]+=y,sum[x]+=siz[x]*y,tgb[x]+=y;}
il vd down(int&x){
if(!x)return;
if(tgd[x])tgd[x]=0,Set(ls[x],tgc[x]),Set(rs[x],tgc[x]);
if(tga[x])Adda(ls[x],tga[x]),Adda(rs[x],tga[x]),Addb(rs[x],tga[x]*(siz[ls[x]]+1)),tga[x]=0;
if(tgb[x])Addb(ls[x],tgb[x]),Addb(rs[x],tgb[x]),tgb[x]=0;
}
il vd upd(int&x){
if(!x)return;
down(ls[x]),down(rs[x]);
siz[x]=siz[ls[x]]+siz[rs[x]]+1,sum[x]=sum[ls[x]]+sum[rs[x]]+w[x];
}
il int merge(int x,int y){
if(x==0||y==0)return x|y;
if(ran[x]<ran[y]){down(x),rs[x]=merge(rs[x],y),upd(x);return x;}
else {down(y),ls[y]=merge(x,ls[y]),upd(y);return y;}
}
il pr split(int&x,int k){
if(!x)return make_pair(0,0);
down(x);
pr y=make_pair(ls[x],rs[x]);
if(k==siz[ls[x]]){ls[x]=0,upd(x),y.second=x;return y;}
if(k==siz[ls[x]]+1){rs[x]=0,upd(x),y.first=x;return y;}
if(k<siz[ls[x]]){y=split(ls[x],k);ls[x]=y.second,upd(x),y.second=x;return y;}
else {y=split(rs[x],k-siz[ls[x]]-1);rs[x]=y.first,upd(x),y.first=x;return y;}
}
int main(){
#ifdef xzz
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
n=gi(),m=gi();
srand(2);ran[0]=rand();
for(rg int i=1;i<=n;++i)ran[i]=(ran[i-1]*19260817ll)&2147483647,w[i]=sum[i]=gi(),siz[i]=1,rt=merge(rt,i);
int l,r,k,opt;
pr a,b;
while(m--){
opt=gi();
if(opt==1){
l=gi(),r=gi(),k=gi();
a=split(rt,l-1),b=split(a.second,r-l+1);
Set(b.first,k);
rt=merge(a.first,merge(b.first,b.second));
}else if(opt==2){
l=gi(),r=gi(),k=gi();
a=split(rt,l-1),b=split(a.second,r-l+1);
Adda(b.first,k);
rt=merge(a.first,merge(b.first,b.second));
}else if(opt==3){
l=gi();a=split(rt,l-1);
++n;ran[n]=(ran[n-1]*19260817ll)&2147483647;
w[n]=sum[n]=gi(),siz[n]=1;
rt=merge(a.first,merge(n,a.second));
}else{
l=gi(),r=gi();
a=split(rt,l-1),b=split(a.second,r-l+1);
printf("%lld
",sum[b.first]);
rt=merge(a.first,merge(b.first,b.second));
}
}
return 0;
}