hdu 4348 To the moon(主席树区间操作)

题目链接：hdu 4348 To the moon

题意:

给你n个数，有m个操作。

1.给区间[l,r]的所有数+d，并且时间戳+1

2.询问当前时间戳的区间和。

3.询问过去时间戳t的区间和。

4.退回到时间戳t。

题解：

直接上主席树。

不过区间操作的时候push_down空间似乎不是那么够用。

所有把push_down这个操作去掉。

用一个标记记录当前这个区间的累加。

询问的时候就将这个累加传下去。(具体看代码)

最后还有退回状态t的时候可以把cnt=root[t+1],

因为后面的内存已经不会再用了。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1e5+7;
 7 struct node{int l,r,lazy;ll sum;}T[N*40];
 8 int n,m,cnt,root[N],now;
 9 
10 void build(int &rt,int l=1,int r=n)
11 {
12     T[rt=++cnt].lazy=0;
13     if(l==r){scanf("%lld",&T[rt].sum);return;}
14     int m=l+r>>1;
15     build(T[rt].l,l,m),build(T[rt].r,m+1,r);
16     T[rt].sum=T[T[rt].l].sum+T[T[rt].r].sum;
17 }
18 
19 void update(int &x,int y,int L,int R,int v,int l=1,int r=n)
20 {
21     T[x=++cnt]=T[y];
22     if(L<=l&&r<=R){T[x].lazy+=v;return;}
23     int m=l+r>>1;
24     if(L<=m)update(T[x].l,T[y].l,L,R,v,l,m);
25     if(R>m)update(T[x].r,T[y].r,L,R,v,m+1,r);
26     int ll=max(L,l),rr=min(R,r);
27     T[x].sum+=1ll*(rr-ll+1)*v;
28 }
29 
30 ll query(int L,int R,int rt,ll add=0,int l=1,int r=n)
31 {
32     if(L<=l&&r<=R)return T[rt].sum+(T[rt].lazy+add)*(r-l+1);
33     int m=l+r>>1;ll an=0;
34     if(L<=m)an+=query(L,R,T[rt].l,add+T[rt].lazy,l,m);
35     if(R>m)an+=query(L,R,T[rt].r,add+T[rt].lazy,m+1,r);
36     return an;
37 }
38 
39 int main()
40 {
41     while(~scanf("%d%d",&n,&m))
42     {
43         cnt=0,now=0,build(root[0]);
44         F(i,1,m)
45         {
46             char op[2];
47             scanf("%s",op);
48             if(op[0]=='C')
49             {
50                 int l,r,d;
51                 now++;
52                 scanf("%d%d%d",&l,&r,&d);
53                 update(root[now],root[now-1],l,r,d);
54             }
55             else if(op[0]=='Q')
56             {
57                 int l,r;
58                 scanf("%d%d",&l,&r);
59                 printf("%lld
",query(l,r,root[now]));
60             }
61             else if(op[0]=='H')
62             {
63                 int l,r,t;
64                 scanf("%d%d%d",&l,&r,&t);
65                 printf("%lld
",query(l,r,root[t]));
66             }else scanf("%d",&now),cnt=root[now+1];
67         }
68     }
69     return 0;
70 }

View Code