hdu 4348 To the moon (主席树）

hdu 4348

题意：

　　一个长度为n的数组，4种操作：

　　　　（1）C l r d：区间[l,r]中的数都加1，同时当前的时间戳加1 。

　　　　（2）Q l r：查询当前时间戳区间[l,r]中所有数的和。

　　　　（3）H l r t：查询时间戳t区间[l,r]的和。

　　　　（4）B t：将当前时间戳置为t 。

　　所有操作均合法。

解法：

　　很明显是一道主席树的题。

　　对于每一次区间加法都新建节点建一棵线段树，加个懒惰标记就行了，查询的话直接线段树区间求和。

　　不过感觉这一题就是为可持续化数据结构写的，特别是时间戳这一点，当前时间戳的版本就是从上一个时间戳继承下来的，而且所有记录都保存了下来，好神奇，感觉对主席树的理解又加深了一点。

code 主席树

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <queue>

 #include <set>

 #include <vector>

 #include <map>

 #define ll long long

 using namespace std;

 const int N=+;

 int root[N],tot;

 int Ls[N*],Rs[N*],add[N*];

 ll sum[N*];

 int n,m;

 inline int bulidtree(int L,int R){

     int k=tot++;

     add[k]=;

     if (L==R){

         scanf("%lld",&sum[k]);

         return k;

     }

     int mid=(L+R)>>;

     Ls[k]=bulidtree(L,mid);

     Rs[k]=bulidtree(mid+,R);

     sum[k]=sum[Ls[k]]+sum[Rs[k]];

     return k;

 }

 inline int update(int o,int L,int R,int x,int LL,int RR){

     int k=tot++;

     Ls[k]=Ls[o]; Rs[k]=Rs[o]; add[k]=add[o]; sum[k]=sum[o];

     sum[k]+=(ll)x*(R-L+);    

     if (LL==L && RR==R){

         add[k]+=x;

         return k;

     }

     int mid=(LL+RR)>>;

     if (R<=mid) Ls[k]=update(Ls[k],L,R,x,LL,mid);

     else if (L>mid) Rs[k]=update(Rs[k],L,R,x,mid+,RR);

     else {

         Ls[k]=update(Ls[k],L,mid,x,LL,mid);

         Rs[k]=update(Rs[k],mid+,R,x,mid+,RR);

     }

     return k;

 }

 inline ll query(int o,int L,int R,int LL,int RR){

     if (L==LL && R==RR) return sum[o];

     int mid=(LL+RR)>>;

     ll ret=(ll)add[o]*(R-L+);

     if (R<=mid) return ret+query(Ls[o],L,R,LL,mid);

     else if (L>mid) return ret+query(Rs[o],L,R,mid+,RR);

     else return ret+query(Ls[o],L,mid,LL,mid)+query(Rs[o],mid+,R,mid+,RR);

 }

 int main(){

     int x,L,R;

     int now;

     char ch[];

     bool f=false;

     while (~scanf("%d%d",&n,&m)){

         if (f) puts("");

         else f=true;

         tot=;

         root[]=bulidtree(,n);

         now=;

         while (m--){

             scanf("%s",ch);

             if (ch[]=='C') {

                 scanf("%d%d%d",&L,&R,&x);

                 now++;

                 root[now]=update(root[now-],L,R,x,,n);

             }

             else if (ch[]=='Q') {

                 scanf("%d%d",&L,&R);

                 printf("%lld\n",query(root[now],L,R,,n));

             }

             else if (ch[]=='H'){

                 scanf("%d%d%d",&L,&R,&x);

                 printf("%lld\n",query(root[x],L,R,,n));

             }

             else if (ch[]=='B') {

                 scanf("%d",&now);

             }

         }

     }

     return ;

 }

巴特西

hdu 4348 To the moon (主席树）

最新文章

热门文章