To the moon(題面原來就是英文，不是我改的)
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.
Description
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 {Ai | 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 {Ai | l <= i <= r}.
3. H l r t: Querying a history sum of {Ai | 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.
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.
Format
Input
N M
A1 A2 ... An
... (Here following the m operations. )
Output
... (For each query, simply print the result. )
Sample 1
Input 1
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
Output 1
4
55
9
15
Sample 2
Input 2
2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1
Output 2
0
1
Limitation
1s, 262144KiB for each test case.
Hint
N, M ≤ 10^5, |A[i]| ≤ 10^9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10^4
若懷疑程序被卡常數，請參見To the moon(時間限制寬鬆)(題面原來就是英文，不是我改的)
附機翻題面
背景
月球是2011年11月發布的一款獨立遊戲，它是由RPG製造商提供的角色扮演冒險遊戲。
月球的前提是基於一種技術，它允許我們永久地重建垂死的人的記憶。在這個問題中，我們將給您一個機會，來實現場景背後的邏輯。
描述
你已經得到N個整數A[1]，A[2]，…，A[N]。在這些整數上，您需要實現以下操作:
1.工作C l r d:為每個{Ai | l <= r}添加一個常數d，並將時間戳增加1，這是唯一會導致時間戳增加的操作。
2.問:查詢當前的{Ai | l <= r}。
3.項目H l r t:查詢歷史的總和。
4.B t:回到t時代，一旦你決定回到過去，你就再也不能進入正版了。
系統從0開始,第一個修改是在時間1 t≥0,不會把你介紹給一個未來的狀態。
格式
輸入
N M
A1 A2……An
……(以下是m操作。)
輸出
……(對於每個查詢，只需打印結果。)
C++ Code
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;
long long n,m,st_size;
long long a[3000000+1];
long long st_t[3000000+1];
long long st_l[3000000+1];
long long st_r[3000000+1];
long long st_mid[3000000+1];
long long st_lc[3000000+1];
long long st_rc[3000000+1];
long long st_sum[3000000+1];
long long st_lazy[3000000+1];
void push_up_1(long long now)
{
st_sum[now]=st_sum[st_lc[now]]+st_sum[st_rc[now]]+((st_r[now]-st_l[now]+1)*st_lazy[now]);
}
void build_st_1(long long &now,long long l,long long r)
{
now=++st_size;
st_l[now]=l;
st_r[now]=r;
st_mid[now]=(l+r)/2;
if (l==r)
st_sum[now]=a[l];
else if (l<r)
{
if (l<=st_mid[now])
build_st_1(st_lc[now],l,st_mid[now]);
if (st_mid[now]+1<=r)
build_st_1(st_rc[now],st_mid[now]+1,r);
push_up_1(now);
}
}
void copy_1(long long now,long long last)
{
st_l[now]=st_l[last];
st_r[now]=st_r[last];
st_mid[now]=st_mid[last];
st_lc[now]=st_lc[last];
st_rc[now]=st_rc[last];
st_sum[now]=st_sum[last];
st_lazy[now]=st_lazy[last];
}
void update_st_1(long long &now,long long last,long long l,long long r,long long d)
{
now=++st_size;
copy_1(now,last);
if (st_l[now]==l&&r==st_r[now])
{
st_sum[now]+=((r-l+1)*d);
st_lazy[now]+=d;
}
else
{
if (r<=st_mid[now])
update_st_1(st_lc[now],st_lc[last],l,r,d);
else if (st_mid[now]+1<=l)
update_st_1(st_rc[now],st_rc[last],l,r,d);
else
{
update_st_1(st_lc[now],st_lc[last],l,st_mid[now],d);
update_st_1(st_rc[now],st_rc[last],st_mid[now]+1,r,d);
}
push_up_1(now);
}
}
long long ask_st_sum_1(long long now,long long l,long long r,long long lazy_d)
{
if (st_l[now]==l&&r==st_r[now])
return st_sum[now]+((r-l+1)*lazy_d);
else if (r<=st_mid[now])
return ask_st_sum_1(st_lc[now],l,r,lazy_d+st_lazy[now]);
else if (st_mid[now]+1<=l)
return ask_st_sum_1(st_rc[now],l,r,lazy_d+st_lazy[now]);
else
return ask_st_sum_1(st_lc[now],l,st_mid[now],lazy_d+st_lazy[now])+ask_st_sum_1(st_rc[now],st_mid[now]+1,r,lazy_d+st_lazy[now]);
}
int main()
{
while (~scanf("%lld%lld",&n,&m))
{
for (long long i=1;i<=n;i++)
scanf("%lld",&a[i]);
st_size=0;
memset(st_t,0,sizeof(st_t));
memset(st_l,0,sizeof(st_l));
memset(st_r,0,sizeof(st_r));
memset(st_mid,0,sizeof(st_mid));
memset(st_lc,0,sizeof(st_lc));
memset(st_rc,0,sizeof(st_rc));
memset(st_sum,0,sizeof(st_sum));
memset(st_lazy,0,sizeof(st_lazy));
build_st_1(st_t[st_size],1,n);
for (long long i=1,tag=0;i<=m;i++)
{
char o;
for (o='$';o!='C'&&o!='Q'&&o!='H'&&o!='B';o=getchar())
;
if (o=='C')
{
tag++;
long long l,r,d;
scanf("%lld%lld%lld",&l,&r,&d);
update_st_1(st_t[tag],st_t[tag-1],l,r,d);
}
else if (o=='Q'||o=='H')
{
long long l,r,t;
scanf("%lld%lld",&l,&r);
if (o=='H')
scanf("%lld",&t);
else
t=tag;
printf("%lld\n",ask_st_sum_1(st_t[t],l,r,0));
}
else if (o=='B')
{
long long t;
scanf("%lld",&t);
tag=t;
}
}
}
}
Source
Vijos Original
