SP11470

· · 个人记录

很喜欢群友的一句话： 看到这里没有标记下传的题解，故来水一篇

我看其他题解大多说下传会破坏复杂度，要么说会空间爆炸，但其实这题不会，但是要是卡的话就老老实实推标永的柿子吧，本文只是给出一种不用推标永的方法

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;
}