很喜欢群友的一句话：
看到这里没有标记下传的题解，故来水一篇
\(Warning:\)代码自己写的，有错请指出，如果您有更好写的方法，也十分欢迎与我交流
我看其他题解大多说下传会破坏复杂度，要么说会空间爆炸，但其实这题不会，但是要是卡的话就老老实实推标永的柿子吧，本文只是给出一种不用推标永的方法
PS：标永无法维护线段树2
好的，让我们进入正题，直接下传是不行的，因为会影响历史版本，所以就如同上面的那句话，下传的时候新建节点就可以了
具体一点，假如我们要下传当前节点的标记，那就新建两个节点，分别赋上当前节点的左右节点的各种值，然后把这两个节点接到当前节点上去，再正常下传就可以了
没了，真没了
但是一到实际的来说，实现就有了一些问题，具体来说，就是啥时候新建节点
主席树一般的写法是在修改的时候无论如何都要新建节点，从历史版本继承，但是由于在下传的时候我们已经新建了节点，而且不能去更新历史版本，所以相当于白下传了
解决方法是什么呢，非常暴力，我们只有在当前节点为空的时候才新建节点，并且在 pushdown 的时候就算没有标记也直接把当前的两个儿子建出来，这样就是对的了
实际表现：
可以看出，空间消耗确实不小也就十倍吧，但是时间上并没有明显差距
代码：
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <stack>
#include <tuple>
#include <bitset>
#define ll long long
#define ull unsigned long long
#define ld long double
#define fp(a,b,c) for(ll a=b;a<=c;a++)
#define fd(a,b,c) for(ll a=b;a>=c;a--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 0x3f3f3f3f
#define base 127
#define mod 1000000007
#define eb emplace_back
#define pb pop_back
#define y1 y114
#define y0 y514
#define x1 x114
#define x0 x514
#define fill(x,y) memset(x,y,sizeof(x))
#define mpr make_pair
#define met(x,t) memset(x,t,sizeof(x))
#define fir first
#define sec second
#define l(now) son[0][now]
#define r(now) son[1][now]
#define endl '\n'
using namespace std;
inline int rd(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')x = (x<<1) + (x<<3) + (ch^48),ch = getchar();
return x * f;}
const int N=1e7+10;
int n,q;
int root[N],a[N],wh[N];
struct node{
int son[2][N],idx=0;
ll tag[N],data[N];;
void cop(int now,int last){
son[0][now]=son[0][last],
son[1][now]=son[1][last],
data[now]=data[last],tag[now]=tag[last];
}
void build(int &now,int l,int r){
now=++idx;
if(l==r) return data[now]=a[l],void();
int mid(l+r>>1);
build(l(now),l,mid),build(r(now),mid+1,r);
data[now]=data[l(now)]+data[r(now)];
}
void pushdown(int now,int l,int r){
int mid(l+r>>1);
cop(++idx,l(now));
l(now)=idx;
cop(++idx,r(now));
r(now)=idx;
tag[l(now)]+=tag[now],
tag[r(now)]+=tag[now];
data[l(now)]+=tag[now]*(mid-l+1);
data[r(now)]+=tag[now]*(r-mid);
tag[now]=0;
}
void modify(int &now,int last,int l,int r,int ql,int qr,int x){
if(!now) now=++idx,cop(now,last);
if(ql<=l&&r<=qr){
tag[now]+=x,data[now]+=(r-l+1)*x;
return ;
}
int mid(l+r>>1);
pushdown(now,l,r);
if(ql<=mid) modify(l(now),l(last),l,mid,ql,qr,x);
if(qr>mid) modify(r(now),r(last),mid+1,r,ql,qr,x);
data[now]=data[l(now)]+data[r(now)];
}
ll query(int now,int l,int r,int ql,int qr){
if(!now) return 0;
if(ql<=l&&r<=qr) return data[now];
int mid(l+r>>1);
pushdown(now,l,r);
if(qr<=mid) return query(l(now),l,mid,ql,qr);
else if(ql>mid) return query(r(now),mid+1,r,ql,qr);
else return query(l(now),l,mid,ql,qr)+query(r(now),mid+1,r,ql,qr);
}
}seg;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=rd(),q=rd();
int tim=0,now=0;
fp(i,1,n) a[i]=rd();
seg.build(root[0],1,n);
while(q--){
char c=getchar();
while(isspace(c)) c=getchar();
int l,r,t;
if(c=='C'){
l=rd(),r=rd(),t=rd(),wh[++now]=++tim;
seg.modify(root[tim],root[tim-1],1,n,l,r,t);
}
else if(c=='Q'){
l=rd(),r=rd();
cout << seg.query(root[tim],1,n,l,r) << endl;
}
else if(c=='H'){
l=rd(),r=rd(),t=rd();
cout << seg.query(root[wh[t]],1,n,l,r) << endl;
}
else now=rd(),root[++tim]=root[wh[now]];
}
return 0;
}