hdu4348（主席树区间修改）

Problem - 4348 (hdu.edu.cn)
Background
To The Moon是一款独立游戏，于2011年11月发布，是一款由RPG Maker提供支持的角色扮演冒险游戏。
《去月球》的前提是基于一种技术，该技术使我们能够永久地重建垂死之人的记忆。在这个问题上，我们将给你一个机会，实现幕后的逻辑。

您已经获得了 N 个整数 A_[1]、A_[2],..., A_[N]。在这些整数上，您需要实现以下操作：
1. C l r d：为每个 {A_i | l <= i <= r} 添加一个常量 d，并将时间戳增加 1，这是唯一会导致时间戳增加的操作。
2. Q l r：查询 {A_i | l <= i <= r} 的当前和。
3. H l r t：查询时间 t.4
中 {A_i | l <= i <= r} 的历史总和。B t：回到时间 t。一旦你决定回到过去，你就再也无法访问前期版本了。
..N， M ≤ 10⁵， |答_[i]|≤ 10⁹， 1 ≤ l ≤ r ≤ N， |d|≤ 10⁴ ..系统从时间 0 开始，第一次修改是在时间 1 t≥ 0，并且不会将您引入未来状态。

输入

输出

思路

使用主席树处理版本控制。由于涉及到区间修改，考虑使用懒标记，在区间更新的时候顺带求出区间和，避免传递懒标记可以节省时间，实测500多ms跑完。

  1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  2 #define bug(x) cout<<#x<<" is "<<x<<endl
  3 #include <iostream>
  4 #include <list>
  5 #include <unordered_map>
  6 #include <map>
  7 #include <vector>
  8 #include <sstream>
  9 #include <cmath>
 10 #include <algorithm>
 11 #define iter ::iterator
 12 using namespace  std;
 13 typedef long long ll;
 14 typedef pair<int,int>P;
 15 #define pb push_back
 16 #define mk make_pair
 17 #define se second
 18 #define fi first
 19 const ll mod=1e9+7;
 20 const int N=1e5+5;
 21 int n,q;
 22 int a[N],rt[N*25],ls[N*25],rs[N*25];
 23 ll sum[N*25],add[N*25];
 24 int cnt;
 25 void build(int &o,int l,int r){
 26     o=++cnt;
 27     if(l==r){
 28         sum[o]=a[l];
 29         return;
 30     }
 31     int m=(l+r)/2;
 32     build(ls[o],l,m);
 33     build(rs[o],m+1,r);
 34     sum[o]=sum[ls[o]]+sum[rs[o]];
 35 }
 36 void up(int &o,int pre,int l,int r,int ql,int qr,int val){
 37     o=++cnt;
 38     ls[o]=ls[pre];
 39     rs[o]=rs[pre];
 40     add[o]=add[pre];
 41     sum[o]=sum[pre]+1ll*val*(min(r,qr)-max(l,ql)+1);
 42     if(l>=ql&&r<=qr){
 43         add[o]+=val;
 44         return;
 45     }
 46     int m=(l+r)/2;
 47     if(ql<=m)up(ls[o],ls[pre],l,m,ql,qr,val);
 48     if(qr>m)up(rs[o],rs[pre],m+1,r,ql,qr,val);
 49 
 50 }
 51 ll qu(int o,int l,int r,int ql,int qr){
 52     if(l>=ql&&r<=qr)return sum[o];
 53     ll res=add[o]*(min(r,qr)-max(l,ql)+1);
 54     int m=(l+r)/2;
 55     if(ql<=m)res+=qu(ls[o],l,m,ql,qr);
 56     if(qr>m)res+=qu(rs[o],m+1,r,ql,qr);
 57     return res;
 58 }
 59 int main(){
 60     while(~scanf("%d%d",&n,&q)){
 61         for(int i=1;i<=n;i++)scanf("%d",&a[i]);
 62         cnt=0;
 63         build(rt[0],1,n);
 64         int time=0;
 65         while(q--){
 66             char op;
 67             int L,R,val;
 68             scanf(" %c",&op);
 69             if(op=='Q'){
 70                 scanf("%d%d",&L,&R);
 71                 ll ans=qu(rt[time],1,n,L,R);
 72                 printf("%lld\n",ans);
 73             }
 74             else if(op=='C'){
 75                 scanf("%d%d%d",&L,&R,&val);
 76                 ++time;
 77                 up(rt[time],rt[time-1],1,n,L,R,val);
 78                 
 79             }
 80             else if(op=='H'){
 81                 scanf("%d%d%d",&L,&R,&val);
 82                 ll ans=qu(rt[val],1,n,L,R);
 83                 printf("%lld\n",ans);
 84             }
 85             else{
 86                 scanf("%d",&val);
 87                 time=val;
 88             }
 89         }
 90         printf("\n");
 91     }
 92 
 93 }
 94 /*
 95 10 100
 96 1 2 3 4 5 6 7 8 9 10
 97 Q 1 10
 98 C 3 6 3
 99 Q 1 10
100 Q 4 4
101 Q 1 10
102 Q 2 4
103 C 3 6 3
104 Q 2 4
105 */