FHQ求条，MLE

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
struct node{int ls,rs,pri,size;ll key,lazy,sum;}t[1000005];
int cnt,root,mt[1000005],num;
inline int newNode(int x){
	t[++cnt].key=x;
	t[cnt].sum=x;
	t[cnt].size=1;
	t[cnt].pri=rand();
	return cnt;
}
inline void Update(int u){
	t[u].size=t[t[u].ls].size+1+t[t[u].rs].size;
	t[u].sum=t[t[u].ls].sum+t[u].key+t[t[u].rs].sum;
}
inline void change(int u,int x){
	t[u].key+=x;
	t[u].lazy+=x;
	t[u].sum+=t[u].size*x;
}
inline void push_down(int u){
    if(t[u].lazy){
        if(t[u].ls){
            int nls=++cnt;
            t[nls]=t[t[u].ls];
            t[u].ls=nls;
            change(t[u].ls,t[u].lazy);
        }
        if(t[u].rs){
            int nrs=++cnt;
            t[nrs]=t[t[u].rs];
            t[u].rs=nrs;
            change(t[u].rs,t[u].lazy);
        }
        t[u].lazy=0;
    }
}
inline void Split(int u,int k,int &L,int &R){
	if(!u){L=R=0;return ;}
	int rt=++cnt;
	t[rt]=t[u];
	push_down(rt);
	if(k<=t[t[u].ls].size){
		R=rt;
		Split(t[rt].ls,k,L,t[rt].ls);
	}
	else {
		L=rt;
		Split(t[rt].rs,k-t[t[u].ls].size-1,t[rt].rs,R);
	}
	Update(rt);
}
inline int Merge(int L,int R){
	if(!L||!R)return L+R;
	if(t[L].pri>t[R].pri){
		push_down(L);
		t[L].rs=Merge(t[L].rs,R);
		Update(L);
		return L;
	}
	else {
		push_down(R);
		t[R].ls=Merge(L,t[R].ls);
		Update(R);
		return R;
	}
}
inline void dfs(int u){
	if(!u)return ;
	change(t[u].ls,t[u].lazy);
	change(t[u].rs,t[u].lazy);
	dfs(t[u].ls);
	mt[++num]=t[u].key;
	dfs(t[u].rs);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>n>>m;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		root=Merge(root,newNode(x));
	}
	while(m--){
		ll op,l1,r1,l2,r2,d;
		cin>>op>>l1>>r1;
		if(op==1){
			cin>>d;
			int L,R,p;
			Split(root,r1,L,R);
			Split(L,l1-1,L,p);
			change(p,d);
			root=Merge(Merge(L,p),R);
		}
		if(op==2){
			cin>>l2>>r2;
			int L1,R1,p1,L2,R2,p2;
			Split(root,r2,L1,R1);
			Split(L1,l2-1,L1,p1);
			Split(root,r1,L2,R2);
			Split(L2,l1-1,L2,p2);
			root=Merge(Merge(L2,p1),R2);
		}
		if(op==3){
			int L,R,p;
			Split(root,r1,L,R);
			Split(L,l1-1,L,p);
			cout<<t[p].sum<<'\n';
			root=Merge(Merge(L,p),R);
		}
		if(cnt>=200005){
			num=0;dfs(root);cnt=0;root=0;
			for(int i=1;i<=num;i++)root=Merge(root,newNode(mt[i]));
		}
	}
	return 0;
}