To the moon

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 5117 Accepted Submission(s): 1152

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₂ ... A_n
... (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

2012 Multi-University Training Contest 5

题意:对于一个长度为n的序列执行4种操作

C l r d 区间[l,r]的数全部增加d 并且当前时刻增加一

Q l r 求区间[l,r]的和

H l r t 求第t个时刻

B t 返回第t个时刻

题解:据说是主席树区间更新入门题目。

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <map>

 #define ll  __int64

 #define mod 1000000007

 #define dazhi 2147483647

 #define N 530005

 using namespace  std;

 ll a[N];

 char s[];

 struct chairmantree

 {

     int rt[*N],ls[*N],rs[*N];

     ll sum[N*],lazy[*N];

     int tot;

     void init()

     {

         tot=;

     }

     void pushup(int l,int r,int pos)

     {

         sum[pos]=sum[ls[pos]]+sum[rs[pos]]+1LL*(r-l+)*lazy[pos];

     }

     void buildtree(int l,int r,int &pos)

     {

         pos=++tot;

         lazy[pos]=;

         sum[pos]=;

         if(l==r)

         {

             sum[pos]=a[l];

             return ;

         }

         int mid=(l+r)>>;

         buildtree(l,mid,ls[pos]);

         buildtree(mid+,r,rs[pos]);

         pushup(l,r,pos);

     }

     void update(int L,int R,ll c,int pre,int l,int r,int &pos)

     {

         pos=++tot;

         ls[pos]=ls[pre];

         rs[pos]=rs[pre];

         sum[pos]=sum[pre];

         lazy[pos]=lazy[pre];

         if(L==l&&R==r)

         {

             sum[pos]+=1LL*(r-l+)*c;

             lazy[pos]+=c;

             return ;

         }

         int mid=(l+r)>>;

         if(R<=mid)

             update(L,R,c,ls[pre],l,mid,ls[pos]);

         else

         {

             if(L>mid)

                 update(L,R,c,rs[pre],mid+,r,rs[pos]);

             else

             {

                 update(L,mid,c,ls[pre],l,mid,ls[pos]);

                 update(mid+,R,c,rs[pre],mid+,r,rs[pos]);

             }

         }

         pushup(l,r,pos);

     }

     ll query(int L,int R,int l,int r,int pos)

     {

         if(L==l&&R==r)

             return sum[pos];

         int mid=(l+r)>>;

         ll ans=1LL*lazy[pos]*(R-L+);

         if(R<=mid)

             ans+=query(L,R,l,mid,ls[pos]);

         else

         {

             if(L>mid)

                 ans+=query(L,R,mid+,r,rs[pos]);

             else

             {

                 ans+=query(L,mid,l,mid,ls[pos]);

                 ans+=query(mid+,R,mid+,r,rs[pos]);

             }

         }

         return ans;

     }

 } tree;

 int main()

 {

     int n,m;

     while(scanf("%d %d",&n,&m)!=EOF)

     {

         for(int i=; i<=n; i++)

             scanf("%I64d",&a[i]);

         tree.init();

         tree.buildtree(,n,tree.rt[]);

         int now=;

         while(m--)

         {

             scanf("%s",s);

             if(s[]=='C')

             {

                 int l,r;

                 ll c;

                 scanf("%d%d%I64d",&l,&r,&c);

                 tree.update(l,r,c,tree.rt[now],,n,tree.rt[now+]);

                 now++;

             }

             if(s[]=='Q')

             {

                 int l,r;

                 scanf("%d %d",&l,&r);

                 printf("%I64d\n",tree.query(l,r,,n,tree.rt[now]));

             }

             if(s[]=='H')

             {

                 int l,r,t;

                 scanf("%d %d %d",&l,&r,&t);

                 printf("%I64d\n",tree.query(l,r,,n,tree.rt[t]));

             }

             if(s[]=='B')

             {

                 int x;

                 scanf("%d",&x);

                 now=x;

             }

         }

     }

     return ;

 }

巴特西

HDU 4348 主席树区间更新

To the moon

最新文章

热门文章