版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

hdu 4348

題意：

　　一個(gè)長度為n的數(shù)組，4種操作 ：

　　　　（1）C l r d：區(qū)間[l,r]中的數(shù)都加1，同時(shí)當(dāng)前的時(shí)間戳加1 。

　　　　（2）Q l r：查詢當(dāng)前時(shí)間戳區(qū)間[l,r]中所有數(shù)的和 。

　　　　（3）H l r t：查詢時(shí)間戳t區(qū)間[l,r]的和 。

　　　　（4）B t：將當(dāng)前時(shí)間戳置為t 。

　　所有操作均合法 。

解法：

　　很明顯是一道主席樹的題 。

　　對(duì)于每一次區(qū)間加法都新建節(jié)點(diǎn)建一棵線段樹，加個(gè)懶惰標(biāo)記就行了，查詢的話直接線段樹區(qū)間求和 。

　　不過感覺這一題就是為可持續(xù)化數(shù)據(jù)結(jié)構(gòu)寫的，特別是時(shí)間戳這一點(diǎn)，當(dāng)前時(shí)間戳的版本就是從上一個(gè)時(shí)間戳繼承下來的，而且所有記錄都保存了下來，好神奇，感覺對(duì)主席樹的理解又加深了一點(diǎn) 。

?

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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/without-ACM/p/5937261.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的hdu 4348 To the moon (主席树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。