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:
- 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.
- Q l r: Querying the current sum of {A i | l <= i <= r}.
- H l r t: Querying a history sum of {A i | l <= i <= r} in time t.
- 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
n m
A 1 A 2 … 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
题意：给四种不同操作，对于询问操作输出答案，可持久化线段树的板子题把.
思路：没啥思路，直接写主席树，就是会出好多bug,注意点就是：
在回到之前版本的线段树的时候，把总结点编号也给重置一下避免mle
这虽然和线段树的板子题有点像，但是由于是可持久化的，对于当前版本的这颗树的查询操作我们不能把lazy标记推下去，因为我们如果要推下去的话，那么我们查询之前版本的线段树就会出错。因为当前版本也许会和前面版本线段树共享儿子，把lazy推下去改变儿子节点（设编号为x）的值之后，就会出现查询以前版本也查到了x结点，但是此时结点已经被后面lazy标记影响了。所以查询的时候我们应该直接把lazy影响的值返回，比如查询到一个区间[l,r]，这个区间lazy不是0，并且查询区间ql,qr处于这个区间中，那么不推lazy并且又要保持值不变就只能在当前区间就返回一个和：(qr+1-ql) * lazy;
最后就还有一个莫名其妙的就是，在新建一个版本线段树时，采用先找到更新区间然后再用pushup把父结点也更新的做法的话，就会wa,只能够再一遍建树的时候就把每个结点的值都维护好。没想懂为什么。。。
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#define mod (10007)
#define middle (l+r)>>1
#define SIZE 1000000+5
#define lowbit(x) (x&(-x))
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long ll;
typedef long double ld;
const int inf_max = 0x3f3f3f;
const ll Linf = 9e18;
const int maxn = 100000+10;
const long double E = 2.7182818;
const double eps=0.0001;
using namespace std;
inline int read()
{
int f=1,res=0;
char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { res=res*10+ch-'0' ; ch=getchar(); }
return f*res;
}
int ls[maxn*25],cnt,rs[maxn*25],root[maxn],n,m,tim;
ll sum[maxn*25],lazy[maxn*25];
void pushup(int rt,int lchd,int rchd) {
sum[rt] = sum[lchd] + sum[rchd];
}
int build_tree(int l,int r) {
int rt = cnt++;lazy[rt] = 0;sum[rt] = 0;
if(l == r) {
ll t;
scanf("%lld",&t);
sum[rt] = t;
return rt;
}
int mid = middle;
ls[rt] = build_tree(l,mid);
rs[rt] = build_tree(mid+1,r);
pushup(rt,ls[rt],rs[rt]);
return rt;
}
void update(int l,int r,int &now,int last,int ql,int qr,ll val) {
now = cnt++; sum[now] = sum[last];lazy[now] = lazy[last];ls[now] = ls[last];rs[now] = rs[last];
sum[now] += (ll)(qr + 1 - ql) * val;
if(l == ql && r == qr) {
lazy[now] += val;
return ;
}
int mid = middle;
if(qr <= mid) {
update(l,mid,ls[now],ls[last],ql,qr,val);
}else if(ql > mid ){
update(mid+1,r,rs[now],rs[last],ql,qr,val);
}else {
update(l,mid,ls[now],ls[last],ql,mid,val);
update(mid+1,r,rs[now],rs[last],mid+1,qr,val);
}
}
ll query(int l,int r,int now,int ql,int qr) {
if(l == ql && r == qr) {
return sum[now];
}
int mid = middle;
if(qr <= mid ) return query(l,mid,ls[now],ql,qr) + lazy[now] * (ll)(qr + 1 - ql);
else if(ql > mid) return query(mid+1,r,rs[now],ql,qr) + lazy[now] * (ll)(qr + 1 - ql);
else return query(l,mid,ls[now],ql,mid) + query(mid+1,r,rs[now],mid+1,qr) + lazy[now] * (ll)(qr + 1 - ql);
}
void rst() {
cnt = 0;tim = 0;
}
int main()
{
int cas = 0;
while(~scanf("%d%d",&n,&m)) {
if(cas++) printf("\n");
rst();
root[tim] = build_tree(1, n);
for (int i = 1; i <= m; i++) {
char ch;
int l, r, t;
ll d;
cin >> ch;
if (ch == 'C') {
tim++;
scanf("%d%d%lld", &l, &r, &d);
update(1, n, root[tim], root[tim - 1], l, r, d);
} else if (ch == 'Q') {
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, n, root[tim], l, r));
} else if (ch == 'H') {
scanf("%d%d%d", &l, &r, &t);
printf("%lld\n", query(1, n, root[t], l, r));
} else if (ch == 'B') {
scanf("%d", &t);
tim = t;
cnt = root[tim + 1];
}
}
}
return 0;
}