可持久化線段樹總結(jié)

1、可持久化線段樹的總結(jié)by石門中學(xué)柯新宇可持久化線段樹，說白了，就是具有一個個時間的樹鏈。因為修改單點，只會對樹上的一條鏈發(fā)生改變，我們只需記錄更改過的樹鏈即可。我們可以發(fā)現(xiàn)，每次修改單點時，只會影響到一條鏈，只需把鏈 存起來就行了。我才用的方法是：對于每一次修改，開一個root，記錄樹根。（用 指針類型，寫起來比較方便）struct nodelong long s,d; node *left,*right;tree(max n 5)+(max n 3),*rootmax n;node *newno de()t0+; treetO.s二treetO.d=O;treetO.left二treetO.

2、right二tree;return tree+tO;root0=newnode();for(int i=1;i=ti;i+) rooti=newnode();for(int i=1;id+;ro-s+=v;return;int mid=(L+R)1;node *yy=newnode(); / 新開節(jié)點 if(xleft; / 拷貝原來的信息ro-left=yy; / 將新的節(jié)點連給父親結(jié)點 updata(ro-left,L,mid,x,v); else*yy=*ro-right;ro-right=yy; updata(ro-right,mid+1,R,x,v);ro-s=ro-left-s+r

3、o-right-s; /up 操作 ro-d=ro-left-d+ro-right-d;至于，區(qū)間修改，開個懶惰標(biāo)記記一記就好了，不用每次更新都 下發(fā)標(biāo)記(這樣會爆空間的) ，查詢的時候加上祖先的標(biāo)記就好了。有幾道比較經(jīng)典的題，可以用來練練手： 先把可持久化線段樹模板練熟了，做題會事半功倍。因為這都是“套路”Bzoj2588-比較麻煩，離散化加 lea 加 query(r1,r2,r3,r4,1,n,)Bzoj2809離散化Hdu5919Hdu4348Bzoj2809代碼：#include#include#define imin(a,b) (ab)?a:b)#define maxn 10005

4、0using namespace std;int n,m,t0,ti;long long ans;int famaxn,llmaxn;long long cctmaxn;struct aaaaint l,r,d; tmmaxn;struct nodelong long s,d; node *left,*right; tree(maxn5)+(maxn3),*rootmaxn;struct eeeeint fa,pi; long long ci,li; masmaxn; int hmaxn,d0;struct dataint to,next; dmaxn;node *newnode()t0+;

5、treet0.s=treet0.d=0;treet0.left=treet0.right=tree;return tree+t0;bool cmp(int A,int B)return (masA.ci0;p=dp.next) dfs(dp.to);tmyu.r=ti;void updata(node *ro,int L,int R,int x,long long v)if(L=R)ro-d+;ro-s+=v;return; int mid=(L+R)1;node *yy=newnode();if(xleft;ro-left=yy;updata(ro-left,L,mid,x,v); else

6、*yy=*ro-right;ro-right=yy;updata(ro-right,mid+1,R,x,v); ro-s=ro-left-s+ro-right-s; ro-d=ro-left-d+ro-right-d;long long query(node *r1,node *r2,int L,int R,long long M)if(L=R) return imin(r2-d-r1-d),M/cctL); if(r2-s-r1-sd-r1-d;long long xx=r2-left-s-r1-left-s;int mid=(L+R)1;if(xx=M) return query(r1-l

7、eft,r2-left,L,mid,M); else return(r2-left-d-r1-left-d+query(r1-right,r2-right,mid+1,R,M-xx); int main()scanf(%d%d,&n,&m);mas0.li=0; ti=0;tree0.left=tree0.right=tree;for(int i=1;i=n;i+) scanf(%d%lld%lld,&masi.fa,&masi.ci,&masi.li); lli=i; addedge(masi.fa,i);sort(ll+1,ll+1+n,cmp);int last=-1,y0=0;for(

8、int i=1;i=n;i+)if(last!=maslli.ci)y0+; last=maslli.ci;ccty0=maslli.ci;maslli.pi=y0;ti=-1;dfs(0);root0=newnode();for(int i=1;i=ti;i+) rooti=newnode();for(int i=1;i=ti;i+)*rooti=*rooti-1;updata(rooti,1,y0,mastmi.d.pi,mastmi.d.ci);ans=0;for(int i=1;ians)?num*mastmi.d.li:ans;printf(%lldn,ans);4408: Fjoi

9、 2016神秘數(shù)Time Limit: 10 Sec Memory Limit: 128 MB一個可重復(fù)數(shù)字集合S的神秘數(shù)定義為最小的不能被 S的子集的和表示的正整數(shù)。例如 S=1,1,1,4,13，1 = 12 = 1+13 = 1+1+14 = 45 = 4+16 = 4+1+17 = 4+1+1+18無法表示為集合S的子集的和，故集合S的神秘數(shù)為&現(xiàn)給定 n 個正整數(shù) a1.an ， m 個詢問，每次詢問給定一個區(qū)間l,r(lv=r)，求由al,al+1,ar所構(gòu)成的可重復(fù)數(shù)字集合的神秘數(shù)。Input第一行一個整數(shù)n表示數(shù)字個數(shù)。第二行 n 個整數(shù)，從 1 編號。第三行一個整數(shù)m,表示詢

10、問個數(shù)。以下m行，每行一對整數(shù)l,r，表示一個詢問。Output對于每個詢問,輸出一行對應(yīng)的答案。Sample Input51 2 4 9 1051 11 21 31 41 5Sample Output24888對于 100%的數(shù)據(jù)點，n,m = 100000,刀 ai = 10八9注：很有趣的題，建議不要一開始就看題解，仔細想一想。AC代碼:#include#include#define maxn 100050#define For(a,b,c) for(int a=b;a=c;a+)using namespace std;int n,m0,m,t0;int dmaxn,mpmaxn;str

11、uct datadata *left,*right;int sum; tree80*maxn,*rootmaxn;bool cmp(int a,int b)return (dax | Rsum+=vv;return;int mid=(L+R)1;data *yy=newnode();if(xleft;ro-left=yy;updata(ro-left,L,mid,x,vv); else*yy=*ro-right;ro-right=yy; updata(ro-right,mid+1,R,x,vv);ro-sum=ro-left-sum+ro-right-sum;int query(data *r

12、1,data *r2,int L,int R,int li,int ri)if(liR | riL) return 0;if(li=L & Rsum-r1-sum);int mid=(L+R)1;int x1=query(r1-left,r2-left,L,mid,li,ri);int x2=query(r1-right,r2-right,mid+1,R,li,ri);return (x1+x2);int main()scanf(%d,&n);For(i,1,n) scanf(%d,&di),mpi=i;dn+1=1e9;sort(mp+1,mp+1+n,cmp);int oi=0,p=0;For(i,1,n)oi=(pdmpi)?oi+1:oi;p=dmpi;mpi=oi;m0=oi;scanf(%d,&m);tree0.left=tree0.right=tree;for(int i=1;i=n;i+) rooti=newnode();root0=&tree0;For(ti,1,n)*rootti=*rootti-1;updata(rootti,1,m0,mpti,dti);For(i,1,m)int ll,rr;scanf(%d%d,&ll,&rr);int lose=1,he=0;for(;)int l=0,r=n+1;while(l+11;if(dmm=lose) l=m