To the moon
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 8372 Accepted Submission(s): 1986
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 {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.
.. N, M ≤ 105, |A[i]| ≤ 109, 1 ≤ l ≤ r ≤ N, |d| ≤ 104 .. 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.
A1 A2 ... An
... (here following the m operations. )
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
55
9
15
0
1
长度为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+,R,rson);
return ret;
这道题真的自闭，wa了一晚上，最后发现，延时标记累加的时候，lazy[rt]*(R-L+1)写成了lazy[rt]*(r-l+1)。。。
其他的就是时间回到t的时候，直接将时间的值更新就可以。
代码:
//HDU 4348.To the moon-可持久化线段树-区间更新，延时标记不下传，优化空间
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define lson l,m
#define rson m+1,r int rt[maxn],ls[maxn<<],rs[maxn<<],sz;
ll sum[maxn<<],lazy[maxn<<]; void pushup(int rt,int m)
{
sum[rt]=sum[ls[rt]]+sum[rs[rt]]+(ll)lazy[rt]*m;
} void build(int &rt,int l,int r)
{
rt=++sz;lazy[rt]=;
if(l==r){
scanf("%lld",&sum[rt]);
return ;
} int m=(l+r)>>;
build(ls[rt],lson);
build(rs[rt],rson);
pushup(rt,r-l+);
} void update(int pre,int &rt,int L,int R,int l,int r,ll c)
{
rt=++sz;lazy[rt]=lazy[pre];sum[rt]=sum[pre];
ls[rt]=ls[pre];rs[rt]=rs[pre];
if(L<=l&&r<=R){
lazy[rt]+=c;
sum[rt]+=(ll)c*(r-l+);
return ;
} int m=(l+r)>>;
if(L<=m) update(ls[pre],ls[rt],L,R,lson,c);
if(R> m) update(rs[pre],rs[rt],L,R,rson,c);
pushup(rt,r-l+);
} ll query(int rt,int L,int R,int l,int r)
{
if(L<=l&&r<=R){
return sum[rt];
} //ll ret=(ll)lazy[rt]*(r-l+1);
ll ret=(ll)lazy[rt]*(R-L+);
int m=(l+r)>>;
//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+,R,rson);
return ret;
} char op[]; int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
sz=;memset(rt,,sizeof(rt));
build(rt[],,n);
int tag=;
for(int i=;i<=m;i++){
scanf("%s",op);
if(op[]=='C'){
int l,r;ll c;
scanf("%d%d%lld",&l,&r,&c);
tag++;
update(rt[tag-],rt[tag],l,r,,n,c);
}
else if(op[]=='Q'){
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",query(rt[tag],l,r,,n));
}
else if(op[]=='H'){
int l,r,d;
scanf("%d%d%d",&l,&r,&d);
printf("%lld\n",query(rt[d],l,r,,n));
}
else if(op[]=='B'){
int x;
scanf("%d",&x);
tag=x;
}
}
}
return ;
}
讲道理，这题还是没完全弄明白，还是有点迷糊。
mdzz。。。