这道题一眼看去就是一个可持久化线段树，但是是区间修改，由于wyx说此题复杂度是O(nlogn)的，我就没写树套树，然后就自己yy了一个离线做法。

    我们考虑直接模拟这个过程，对于一个B操作，我们直接将之前的操作的影响清除，这样每个操作最多会被计算2次，但是有一个问题就是H操作不太好弄，我们可以先离线下来，然后维护一下H操作的这个时间t被经过了多少次，这样我们就知道这个H操作是我们第几次模拟后的查询，这样就可以通过一个普通的线段树来维护了。

    这道题好像正解是区间修改的主席树，我之前只会写套上树状数组的，不过感觉这个没什么用...就先不学了吧..

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 #define maxn 100005  7 typedef long long LL;  8 struct tree  9 { 10     int l,r; 11     LL sum,lazy; 12 }t[maxn*4]; 13 struct ask 14 { 15     int opt,l,r,d,t; 16 }q[maxn]; 17 int n,m,T,cnt[maxn],st[maxn],top,cur[maxn],a[maxn]; 18 LL ans[maxn]; 19 vector
         
          
            > g[maxn]; 20 21 inline int read(void) 22 { 23 int x=0,f=1; 24 char ch=getchar(); 25 while (ch>'9'||ch<'0') 26 { 27 if (ch=='-') f=-1; 28 ch=getchar(); 29 } 30 while (ch>='0'&&ch<='9') 31 { 32 x=x*10+ch-'0'; 33 ch=getchar(); 34 } 35 return x*f; 36 } 37 38 void build(int x,int l,int r) 39 { 40 t[x].l=l;t[x].r=r; 41 if (l==r) 42 { 43 t[x].sum=a[l]; 44 return; 45 } 46 int mid=(l+r)>>1; 47 build(2*x,l,mid); 48 build(2*x+1,mid+1,r); 49 t[x].sum=t[2*x].sum+t[2*x+1].sum; 50 } 51 52 void update(int x) 53 { 54 t[2*x].sum+=t[x].lazy*(t[2*x].r-t[2*x].l+1); 55 t[2*x+1].sum+=t[x].lazy*(t[2*x+1].r-t[2*x+1].l+1); 56 t[2*x].lazy+=t[x].lazy; 57 t[2*x+1].lazy+=t[x].lazy; 58 t[x].lazy=0; 59 } 60 61 void change(int x,int l,int r,int z) 62 { 63 if (t[x].l==l&&t[x].r==r) 64 { 65 t[x].sum+=(LL)z*(r-l+1); 66 t[x].lazy+=z; 67 return; 68 } 69 if (t[x].lazy) update(x); 70 int mid=(t[x].l+t[x].r)>>1; 71 if (l>mid) change(2*x+1,l,r,z); 72 else if (r<=mid) change(2*x,l,r,z); 73 else 74 { 75 change(2*x,l,mid,z); 76 change(2*x+1,mid+1,r,z); 77 } 78 t[x].sum=t[2*x].sum+t[2*x+1].sum; 79 } 80 81 LL query(int x,int l,int r) 82 { 83 if (t[x].l==l&&t[x].r==r) return t[x].sum; 84 if (t[x].lazy) update(x); 85 int mid=(t[x].l+t[x].r)>>1; 86 if (l>mid) return query(2*x+1,l,r); 87 else if (r<=mid) return query(2*x,l,r); 88 else return query(2*x,l,mid)+query(2*x+1,mid+1,r); 89 } 90 91 int main() 92 { 93 n=read();m=read(); 94 for (int i=1;i<=n;i++) a[i]=read(); 95 for (int i=1;i<=m;i++) 96 { 97 char s[3]; 98 scanf("%s",s); 99 if (s[0]=='C') 100 {101 q[i].opt=1;cnt[++T]++;102 q[i].l=read();q[i].r=read();q[i].d=read();103 q[i].t=T;104 }105 if (s[0]=='Q') 106 {107 q[i].opt=2;q[i].l=read();108 q[i].r=read();g[T].push_back(make_pair(cnt[T],i));109 q[i].t=T;110 }111 if (s[0]=='H') 112 {113 q[i].opt=3;q[i].l=read();q[i].r=read();114 int t=read();115 g[t].push_back(make_pair(cnt[t],i));116 q[i].t=t;117 }118 if (s[0]=='B') 119 {120 q[i].opt=4;q[i].d=read();q[i].t=T;121 T=q[i].d;122 }123 }124 build(1,1,n);T=0;125 for (int i=1;i<=m;i++) 126 if ((q[i].opt==3||q[i].opt==2)&&q[i].t==0) 127 ans[i]=query(1,q[i].l,q[i].r);128 memset(cnt,0,sizeof cnt);129 for (int i=1;i<=m;i++) 130 {131 if (q[i].opt==2||q[i].opt==3) continue;132 if (q[i].opt==1) 133 {134 cnt[++T]++;135 change(1,q[i].l,q[i].r,q[i].d);136 st[++top]=i;137 int siz=g[T].size();138 while (cur[T]
           
            0&&q[st[top]].t>q[i].d) 148 change(1,q[st[top]].l,q[st[top]].r,-q[st[top]].d),top--;149 T=q[i].d;150 }151 }152 for (int i=1;i<=m;i++) 153 if (q[i].opt==2||q[i].opt==3) printf("%lld\n",ans[i]);154 return 0;155 }