| Time Limit: 2000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
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 5, |A [i]| ≤ 10 9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10 4 .. 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
A 1 A 2 ... A n
... (here following the m operations. )
Output
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
Source
可持久化线段树模板题。
对于不同的时间建立不同的新结点，新结点按照线段树的规则连接各个被修改的结点的新址（修改时不在原结点修改，而是新建一个结点（类似于分层图什么的）），没有修改的区域就直接链接到旧树的结点（因此不能用root*2 root*2+1的方式算结点，而要用数组模拟指针记录子结点标号）。
由于新层和旧层修改的值不一样，所以lazy标记是不能持久化的，一层的lazy只能在一层用。具体的解决方法见代码。
↑看到有大神说lazy标记持久化的方法是，对每个lazy记录时间戳，只有其标记时间与当前所要求的状态的时间相同时，才计算。然而看上去好麻烦。
代码基本靠抄。
看到有人说这题卡内存，就特意把数组开小了，结果依旧MLE。折腾一个多小时无果，怒把数组开到300w，居然A了。
↑想了想，大概MLE是因为动态申请新节点时，因为t数组越界，申请到了超大的节点值，直接炸掉内存，所以MLE而不是RE。
感到内存学问博大精深。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
#define mid (l+r)/2
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m;
int data[mxn];
struct node{
int lc,rc;
LL sum,mk;
}t[];
int root[mxn];
int nct=;
int ntime=;
void Build(int l,int r,int &rt){
t[++nct]=t[rt];
rt=nct;
if(l==r){
t[rt].sum=data[l];
return;
}
Build(l,mid,t[rt].lc);
Build(mid+,r,t[rt].rc);
t[rt].sum=t[t[rt].lc].sum+t[t[rt].rc].sum;
return;
}
void add(int L,int R,int v,int l,int r,int &rt){
t[++nct]=t[rt];
rt=nct;
t[rt].sum+=(LL)v*(min(R,r)-max(l,L)+);
if(L<=l && r<=R){
t[rt].mk+=v;
return;
}
if(L<=mid)add(L,R,v,l,mid,t[rt].lc);
if(R>mid)add(L,R,v,mid+,r,t[rt].rc);
return;
}
LL query(int L,int R,int l,int r,int rt){
if(L<=l && r<=R)return t[rt].sum;
LL res=t[rt].mk*1LL*(min(R,r)-(max(L,l))+);
if(L<=mid)res+=query(L,R,l,mid,t[rt].lc);
if(R>mid)res+=query(L,R,mid+,r,t[rt].rc);
return res;
}
int main(){
char op[];
int i,j,x,y,a;
while(~scanf("%d%d",&n,&m)){
ntime=;nct=;
for(i=;i<=n;i++)
data[i]=read();
Build(,n,root[]);
for(i=;i<=m;i++){
scanf("%s",op);
switch(op[]){
case 'Q':{
x=read();y=read();
printf("%lld\n",query(x,y,,n,root[ntime]));
break;
}
case 'C':{
x=read();y=read();a=read();
++ntime;
root[ntime]=root[ntime-];
add(x,y,a,,n,root[ntime]);
break;
}
case 'H':{
x=read();y=read();a=read();
printf("%lld\n",query(x,y,,n,root[a]));
break;
}
case 'B':{
ntime=read();
break;
}
}
}
}
return ;
}