首页 > 代码库 > hdu 4348 To the moon (主席树）
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 主席树
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <queue> 7 #include <set> 8 #include <vector> 9 #include <map> 10 #define ll long long 11 12 using namespace std; 13 14 const int N=100000+7; 15 16 int root[N],tot; 17 int Ls[N*30],Rs[N*30],add[N*30]; 18 ll sum[N*30]; 19 20 int n,m; 21 22 inline int bulidtree(int L,int R){ 23 int k=tot++; 24 add[k]=0; 25 26 if (L==R){ 27 scanf("%lld",&sum[k]); 28 return k; 29 } 30 31 int mid=(L+R)>>1; 32 Ls[k]=bulidtree(L,mid); 33 Rs[k]=bulidtree(mid+1,R); 34 35 sum[k]=sum[Ls[k]]+sum[Rs[k]]; 36 37 return k; 38 } 39 40 inline int update(int o,int L,int R,int x,int LL,int RR){ 41 int k=tot++; 42 Ls[k]=Ls[o]; Rs[k]=Rs[o]; add[k]=add[o]; sum[k]=sum[o]; 43 44 sum[k]+=(ll)x*(R-L+1); 45 46 if (LL==L && RR==R){ 47 add[k]+=x; 48 return k; 49 } 50 51 int mid=(LL+RR)>>1; 52 if (R<=mid) Ls[k]=update(Ls[k],L,R,x,LL,mid); 53 else if (L>mid) Rs[k]=update(Rs[k],L,R,x,mid+1,RR); 54 else { 55 Ls[k]=update(Ls[k],L,mid,x,LL,mid); 56 Rs[k]=update(Rs[k],mid+1,R,x,mid+1,RR); 57 } 58 59 return k; 60 } 61 62 inline ll query(int o,int L,int R,int LL,int RR){ 63 if (L==LL && R==RR) return sum[o]; 64 65 int mid=(LL+RR)>>1; 66 67 ll ret=(ll)add[o]*(R-L+1); 68 69 if (R<=mid) return ret+query(Ls[o],L,R,LL,mid); 70 else if (L>mid) return ret+query(Rs[o],L,R,mid+1,RR); 71 else return ret+query(Ls[o],L,mid,LL,mid)+query(Rs[o],mid+1,R,mid+1,RR); 72 } 73 74 int main(){ 75 int x,L,R; 76 int now; 77 char ch[3]; 78 79 bool f=false; 80 81 while (~scanf("%d%d",&n,&m)){ 82 if (f) puts(""); 83 else f=true; 84 85 tot=0; 86 root[0]=bulidtree(1,n); 87 now=0; 88 89 while (m--){ 90 scanf("%s",ch); 91 if (ch[0]==‘C‘) { 92 scanf("%d%d%d",&L,&R,&x); 93 now++; 94 root[now]=update(root[now-1],L,R,x,1,n); 95 } 96 else if (ch[0]==‘Q‘) { 97 scanf("%d%d",&L,&R); 98 printf("%lld\n",query(root[now],L,R,1,n)); 99 }100 else if (ch[0]==‘H‘){101 scanf("%d%d%d",&L,&R,&x);102 printf("%lld\n",query(root[x],L,R,1,n));103 }104 else if (ch[0]==‘B‘) {105 scanf("%d",&now);106 }107 }108 }109 110 return 0;111 }
hdu 4348 To the moon (主席树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。