http://acm.hdu.edu.cn/showproblem.php?pid=4348
sb的标记永久化即可，刚开始add和sum没复制过来wa了两发。。。，操作和原来的都一样，出来单点变成区间，还要加一个标记永久化，这样就不用pushdown新加节点而爆内存了
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 //#define ls l,m,rt<<1 //#define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=90000+10,inf=0x3f3f3f3f; int rt[N],tot,ls[N*30],rs[N*30]; ll sum[N*30],add[N*30]; void build(int &o,int l,int r) { o=++tot; add[o]=0; if(l==r) { scanf("%lld",&sum[o]); return ; } int m=(l+r)>>1; build(ls[o],l,m); build(rs[o],m+1,r); sum[o]=sum[ls[o]]+sum[rs[o]]; // printf("%d+++%d+++%d+++%lld+++%d ",l,r,o,sum[o],add[o]); } void update(int &o,int l,int r,int last,int L,int R,int x) { o=++tot; ls[o]=ls[last]; rs[o]=rs[last]; sum[o]=sum[last]; add[o]=add[last]; if(L<=l&&r<=R) { add[o]+=x; return ; } int m=(l+r)>>1; if(L<=m)update(ls[o],l,m,ls[last],L,R,x); if(m<R)update(rs[o],m+1,r,rs[last],L,R,x); sum[o]=sum[ls[o]]+add[ls[o]]*(m-l+1)+sum[rs[o]]+add[rs[o]]*(r-m); // printf("%d %d %lld %lld ",ls[o],rs[o],sum[ls[o]],sum[rs[o]]); // printf("%d+++%d+++%d+++%lld+++%d ",l,r,o,sum[o],add[o]); } ll query(int o,ll ad,int l,int r,int L,int R) { // printf("%d %d %d %lld ",l,r,o,ad); if(L<=l&&r<=R) return (ad+add[o])*(r-l+1)+sum[o]; ll ans=0; int m=(l+r)>>1; if(L<=m)ans+=query(ls[o],ad+add[o],l,m,L,R); if(m<R)ans+=query(rs[o],ad+add[o],m+1,r,L,R); return ans; } char s[10]; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { build(rt[0],1,n); int cnt=0; while(m--) { scanf("%s",s); if(s[0]=='Q') { int l,r; scanf("%d%d",&l,&r); printf("%lld ",query(rt[cnt],0,1,n,l,r)); } else if(s[0]=='C') { cnt++; int l,r,c; scanf("%d%d%d",&l,&r,&c); update(rt[cnt],1,n,rt[cnt-1],l,r,c); } else if(s[0]=='H') { int l,r,c; scanf("%d%d%d",&l,&r,&c); printf("%lld ",query(rt[c],0,1,n,l,r)); } else scanf("%d",&cnt); } } return 0; } /******************** 10 5 1 2 3 4 5 6 7 8 9 10 Q 2 4 C 3 6 3 Q 2 4 ********************/