[HDU 4348]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.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.INPUT
n m
A1 A2 ... An... (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
OUTPUT
4
55
9
15
0
1
解题报告
可。。。可。。。可持久化?
初识可持久化线段树+区间修改
1 #include2 #include 3 #include 4 using namespace std; 5 typedef long long L; 6 inline int read(){ 7 int sum(0),f(1); 8 char ch(getchar()); 9 for(;ch<'0'||ch>'9';ch=getchar()) 10 if(ch=='-') 11 f=-1; 12 for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 13 return sum*f; 14 } 15 int n,m,t,cnt; 16 int v[100005]; 17 int rt[100005],lch[4000005],rch[4000005]; 18 L sum[4000005],add[4000005]; 19 char op[2]; 20 inline int build(int l,int r){ 21 int x(++cnt); 22 add[x]=0; 23 if(l==r){ 24 sum[x]=v[l]; 25 lch[x]=rch[x]=0; 26 // cout<<"pos "< <<" "< <<' '< <<" "< <<' '< < >1); 30 lch[x]=build(l,mid); 31 // cout<<"left child"< <<" "< <<' '< < >1))+add[rch[x]]*(len>>1); 42 } 43 inline int update(int rt,int ll,int rr,L w,int l,int r){ 44 int newrt(++cnt); 45 add[newrt]=add[rt]; 46 if(ll<=l&&r<=rr){ 47 sum[newrt]=sum[rt]; 48 add[newrt]=add[rt]+w; 49 lch[newrt]=lch[rt]; 50 rch[newrt]=rch[rt]; 51 return newrt; 52 } 53 int mid((l+r)>>1); 54 if(ll<=mid) 55 lch[newrt]=update(lch[rt],ll,rr,w,l,mid); 56 else 57 lch[newrt]=lch[rt]; 58 if(mid >1); 70 L ret(0); 71 if(ll<=mid) 72 ret+=query(lch[rt],ll,rr,l,mid,add[rt]+add1); 73 if(mid