To the moon(時間限制寬鬆)(題面原來就是英文，不是我改的)
本題用於驗證To the moon(題面原來就是英文，不是我改的)的程序是否被卡常數，時間限制設置為每個測試點30s，如下是一個差點因為被卡常數而無法通過的程序
C++ Code
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
namespace dts
{
typedef long long ll;
class segtree{
public:
ll size=0;
class st_rec{
public:
ll rt,rtl,rtr;
};
deque<st_rec> rec;
deque<ll> fa,lc,rc,sl,sr,smid,sum,sumlz;
void reszcl(ll sz)
{
size=0;
rec.resize(sz);
fa.clear(),lc.clear(),rc.clear();
sl.clear(),sr.clear(),smid.clear();
sum.clear(),sumlz.clear();
}
void set_st(ll ver,ll l,ll r)
{
rec[ver].rt=-1,rec[ver].rtl=l,rec[ver].rtr=r;
}
ll len(ll now)
{
return sr[now]-sl[now]+1;
}
void update(ll &now,ll last,ll fath,ll ver,ll l,ll r,ll val)
{
if (now==-1||now+1>size)
{
now=size++;
fa.push_back(fath),lc.push_back(-1),rc.push_back(-1);
if (last!=-1)
{
sl.push_back(sl[last]),sr.push_back(sr[last]),smid.push_back(smid[last]);
sum.push_back(sum[last]),sumlz.push_back(sumlz[last]);
}
else
{
sum.push_back(0),sumlz.push_back(0);
if (now==rec[ver].rt)
sl.push_back(rec[ver].rtl),sr.push_back(rec[ver].rtr);
else if (now==lc[fa[now]])
sl.push_back(sl[fa[now]]),sr.push_back(smid[fa[now]]);
else if (now==rc[fa[now]])
sl.push_back(smid[fa[now]]+1),sr.push_back(sr[fa[now]]);
smid.push_back((sl[now]+sr[now])>>1);
}
}
if (last!=-1)
sum[now]=sum[last],sumlz[now]=sumlz[last];
if (sl[now]==l&&r==sr[now])
{
sum[now]+=len(now)*val;
sumlz[now]+=val;
if (lc[now]==-1&&last!=-1)
lc[now]=lc[last];
if (rc[now]==-1&&last!=-1)
rc[now]=rc[last];
}
else
{
if (r<=smid[now])
update(lc[now],(last==-1)?-1:lc[last],now,ver,l,r,val);
else if (smid[now]+1<=l)
update(rc[now],(last==-1)?-1:rc[last],now,ver,l,r,val);
else
{
update(lc[now],(last==-1)?-1:lc[last],now,ver,l,smid[now],val);
update(rc[now],(last==-1)?-1:rc[last],now,ver,smid[now]+1,r,val);
}
if (lc[now]==-1&&last!=-1)
lc[now]=lc[last];
if (rc[now]==-1&&last!=-1)
rc[now]=rc[last];
sum[now]=((lc[now]!=-1)?sum[lc[now]]:0)+((rc[now]!=-1)?sum[rc[now]]:0)+len(now)*sumlz[now];
}
}
ll ask(ll now,ll l,ll r,ll sum_lz)
{
if (now==-1||now+1>size)
return 0;
if (sl[now]==l&&r==sr[now])
return sum[now]+len(now)*sum_lz;
else
{
if (r<=smid[now])
return ask(lc[now],l,r,sum_lz+sumlz[now]);
else if (smid[now]+1<=l)
return ask(rc[now],l,r,sum_lz+sumlz[now]);
else
return ask(lc[now],l,smid[now],sum_lz+sumlz[now])+ask(rc[now],smid[now]+1,r,sum_lz+sumlz[now]);
}
}
};
segtree ltmst;
ll n,m;
vector<ll> a;
void main()
{
while (~scanf("%lld%lld",&n,&m))
{
a.resize(n);
for (ll i=0;i<n;i++)
scanf("%lld",&a[i]);
ltmst.reszcl(1);
ltmst.set_st(0,0,n-1);
for (ll i=0;i<n;i++)
ltmst.update(ltmst.rec[0].rt,-1,-1,0,i,i,a[i]);
for (ll i=1,tag=0;i<=m;i++)
{
char o;
for (o='$';o!='C'&&o!='Q'&&o!='H'&&o!='B';o=getchar())
;
if (o=='C')
{
if ((++tag)+1>ltmst.rec.size())
ltmst.rec.resize(ltmst.rec.size()+1);
ltmst.set_st(tag,0,n-1);
ll l,r,val;
scanf("%lld%lld%lld",&l,&r,&val);
ltmst.update(ltmst.rec[tag].rt,ltmst.rec[tag-1].rt,-1,tag,l-1,r-1,val);
}
else if (o=='Q'||o=='H')
{
ll l,r,t;
scanf("%lld%lld",&l,&r);
if (o=='H')
scanf("%lld",&t);
else
t=tag;
printf("%lld\n",ltmst.ask(ltmst.rec[t].rt,l-1,r-1,0));
}
else if (o=='B')
{
ll t;
scanf("%lld",&t);
tag=t;
}
}
}
}
}
int main()
{
dts::main();
}
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
30s, 262144KiB for each test case.
Hint
N, M ≤ 10^5, |A[i]| ≤ 10^9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10^4
附機翻題面
背景
月球是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操作。)
輸出
……(對於每個查詢，只需打印結果。)
Source
Vijos Original
