HDU 4348.To the moon SPOJ - TTM To the moon -可持久化线段树(带修改在线区间更新(增减)、区间求和、查询历史版本、回退到历史版本、延时标记不下放(空...-白红宇

HDU 4348.To the moon SPOJ - TTM To the moon -可持久化线段树(带修改在线区间更新(增减)、区间求和、查询历史版本、回退到历史版本、延时标记不下放(空...

阅读量：4560 次

发布时间：2019-06-08

本文共 4805 字，大约阅读时间需要 16 分钟。

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 8372 Accepted Submission(s): 1986

Problem Description

Background

To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.

The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we'll give you a chance, to implement the logic behind the scene.

You‘ve been given N integers A

_[1], A

_[2],..., A

_[N]. On these integers, you need to implement the following operations:

1. C l r d: Adding a constant d for every {A

_i | l <= i <= r}, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase.

2. Q l r: Querying the current sum of {A

_i | l <= i <= r}.

3. H l r t: Querying a history sum of {A

_i | l <= i <= r} in time t.

4. B t: Back to time t. And once you decide return to a past, you can never be access to a forward edition anymore.

.. N, M ≤ 10

⁵, |A

_[i]| ≤ 10

⁹, 1 ≤ l ≤ r ≤ N, |d| ≤ 10

⁴ .. the system start from time 0, and the first modification is in time 1, t ≥ 0, and won't introduce you to a future state.

Input

n m

₁ A

₂ ... A

... (here following the m operations. )

Output

... (for each query, simply print the result. )

Sample Input

10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4 2 4 0 0 C 1 1 1 C 2 2 -1 Q 1 2 H 1 2 1

Sample Output

4 55 9 15 0 1

Author

HIT

Source

题意：

长度为n的整数序列，支持四个操作

1：Q l r 输出区间[l,r]的总和

2：C l r x 区间[l,r]的每个值都增加x，此时时间增加1

3：H l r t 询问在t时刻区间[l,r]的总和

4：B t 时间回到t

延时标记如果下传的话，内存不够，所以要节省内存，按照正常的区间更新的操作，标记下传，就新开节点，这道题中，我们不新开节点，用一个标记来记录当前节点的整段区间被累加了多少，当询问的时候，从根节点走到目标节点的过程中累加所经过节点上的标记值就可以。

所以就不能用以前的查询写法，if(L<=m) ... if(R> m) ... ，就需要换一种写法，就是这里:

　　 //if(L<=m) ret+=query(ls[rt],L,R,lson,c);    //if(R> m) ret+=query(rs[rt],L,R,rson,c);    if(R<=m) ret+=query(ls[rt],L,R,lson);    else if(L> m) ret+=query(rs[rt],L,R,rson);    else ret+=query(ls[rt],L,m,lson)+query(rs[rt],m+1,R,rson);    return ret;

这道题真的自闭，wa了一晚上，最后发现，延时标记累加的时候，lazy[rt]*(R-L+1)写成了lazy[rt]*(r-l+1)。。。

其他的就是时间回到t的时候，直接将时间的值更新就可以。

代码:

1 //HDU 4348.To the moon-可持久化线段树-区间更新，延时标记不下传，优化空间  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 #include
             
               10 #include
              
                11 #include
               
                 12 #include
                
                  13 #include
                 
                   14 #include
                  
                    15 #include
                    16 #include
                    
                      17 #include
                     
                       18 #include
                      
                        19 #include
                       
                         20 using namespace std; 21 typedef long long ll; 22 typedef pair
                        
                          pii; 23 24 const double PI=acos(-1.0); 25 const double eps=1e-6; 26 const ll mod=1e9+7; 27 const int inf=0x3f3f3f3f; 28 const int maxn=1e5+10; 29 const int maxm=100+10; 30 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 31 32 #define lson l,m 33 #define rson m+1,r 34 35 int rt[maxn],ls[maxn<<5],rs[maxn<<5],sz; 36 ll sum[maxn<<5],lazy[maxn<<5]; 37 38 void pushup(int rt,int m) 39 { 40 sum[rt]=sum[ls[rt]]+sum[rs[rt]]+(ll)lazy[rt]*m; 41 } 42 43 void build(int &rt,int l,int r) 44 { 45 rt=++sz;lazy[rt]=0; 46 if(l==r){ 47 scanf("%lld",&sum[rt]); 48 return ; 49 } 50 51 int m=(l+r)>>1; 52 build(ls[rt],lson); 53 build(rs[rt],rson); 54 pushup(rt,r-l+1); 55 } 56 57 void update(int pre,int &rt,int L,int R,int l,int r,ll c) 58 { 59 rt=++sz;lazy[rt]=lazy[pre];sum[rt]=sum[pre]; 60 ls[rt]=ls[pre];rs[rt]=rs[pre]; 61 if(L<=l&&r<=R){ 62 lazy[rt]+=c; 63 sum[rt]+=(ll)c*(r-l+1); 64 return ; 65 } 66 67 int m=(l+r)>>1; 68 if(L<=m) update(ls[pre],ls[rt],L,R,lson,c); 69 if(R> m) update(rs[pre],rs[rt],L,R,rson,c); 70 pushup(rt,r-l+1); 71 } 72 73 ll query(int rt,int L,int R,int l,int r) 74 { 75 if(L<=l&&r<=R){ 76 return sum[rt]; 77 } 78 79 //ll ret=(ll)lazy[rt]*(r-l+1); 80 ll ret=(ll)lazy[rt]*(R-L+1); 81 int m=(l+r)>>1; 82 //if(L<=m) ret+=query(ls[rt],L,R,lson,c); 83 //if(R> m) ret+=query(rs[rt],L,R,rson,c); 84 if(R<=m) ret+=query(ls[rt],L,R,lson); 85 else if(L> m) ret+=query(rs[rt],L,R,rson); 86 else ret+=query(ls[rt],L,m,lson)+query(rs[rt],m+1,R,rson); 87 return ret; 88 } 89 90 char op[5]; 91 92 int main() 93 { 94 int n,m; 95 while(~scanf("%d%d",&n,&m)){ 96 sz=0;memset(rt,0,sizeof(rt)); 97 build(rt[0],1,n); 98 int tag=0; 99 for(int i=1;i<=m;i++){100 scanf("%s",op);101 if(op[0]=='C'){102 int l,r;ll c;103 scanf("%d%d%lld",&l,&r,&c);104 tag++;105 update(rt[tag-1],rt[tag],l,r,1,n,c);106 }107 else if(op[0]=='Q'){108 int l,r;109 scanf("%d%d",&l,&r);110 printf("%lld\n",query(rt[tag],l,r,1,n));111 }112 else if(op[0]=='H'){113 int l,r,d;114 scanf("%d%d%d",&l,&r,&d);115 printf("%lld\n",query(rt[d],l,r,1,n));116 }117 else if(op[0]=='B'){118 int x;119 scanf("%d",&x);120 tag=x;121 }122 }123 }124 return 0;125 }

讲道理，这题还是没完全弄明白，还是有点迷糊。

mdzz。。。

转载于:https://www.cnblogs.com/ZERO-/p/9821988.html

你可能感兴趣的文章