可持久化线段树总结

1、可持久化线段树的总结 by石门中学柯新宇 可持久化线段树，说白了，就是具有一个个时间的树链。因为修 改单点，只会对树上的一条链发生改变，我们只需记录更改过的树链 即可。 我们可以发现，每次修改单点时，只会影响到一条链，只需把链 存起来就行了。 我才用的方法是：对于每一次修改，开一个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.l

2、eft二treetO.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(); / 新开节点 if(xleft; / 拷贝原来的信息 ro-left=yy; / 将新的节点连给父亲结点 updata(ro-left,L,mid,x,v); else *yy=*ro-right; ro-right=yy; updata(ro-right,mid+1,R,x

3、,v); ro-s=ro-left-s+ro-right-s; /up 操作 ro-d=ro-left-d+ro-right-d; 至于，区间修改，开个懒惰标记记一记就好了，不用每次更新都 下发标记(这样会爆空间的) ，查询的时候加上祖先的标记就好了。 有几道比较经典的题，可以用来练练手： 先把可持久化线段树模板练熟了，做题会事半功倍。 因为这都是“套路” Bzoj2588-比较麻烦，离散化加 lea 加 query(r1,r2,r3,r4,1,n,) Bzoj2809离散化 Hdu5919 Hdu4348 Bzoj2809代码： #include #include #define imin(

4、a,b) (ab)?a:b) #define maxn 100050 using 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 d

5、ataint to,next; dmaxn; node *newnode() t0+; 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()

6、; if(xleft; ro-left=yy; 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+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=

7、r2-left-s-r1-left-s; int mid=(L+R)1; if(xx=M) return query(r1-left,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, mas0.li=0; ti=0; tree0.left=tree0.right=tree; for(int i=1;i=n;i+) scanf(%d%lld%lld, lli=i; addedge(masi.fa,i); sort(ll+1

8、,ll+1+n,cmp); int last=-1,y0=0; for(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)

9、?num*mastmi.d.li:ans; printf(%lldn,ans); 4408: Fjoi 2016神秘数 Time Limit: 10 Sec Memory Limit: 128 MB 一个可重复数字集合S的神秘数定义为最小的不能被 S的子集的 和表示的正整数。例如 S=1,1,1,4,13， 1 = 1 2 = 1+1 3 = 1+1+1 4 = 4 5 = 4+1 6 = 4+1+1 7 = 4+1+1+1 8无法表示为集合S的子集的和，故集合S的神秘数为a=c;a+) using namespace std; int n,m0,m,t0; int dmaxn,mpmaxn;

10、 struct data data *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;

11、 int query(data *r1,data *r2,int L,int R,int li,int ri) if(liR | riL) return 0; if(li=L 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, For(i,1,n) scanf(%d, dn+1=1e9; sort(mp+1,mp+1+n,cmp); int oi=0,p=0; F

12、or(i,1,n) oi=(pdmpi)?oi+1:oi; p=dmpi; mpi=oi; m0=oi; scanf(%d, tree0.left=tree0.right=tree; for(int i=1;i=n;i+) rooti=newnode(); root0= For(ti,1,n) *rootti=*rootti-1; updata(rootti,1,m0,mpti,dti); For(i,1,m) int ll,rr; scanf(%d%d, int lose=1,he=0; for(;) int l=0,r=n+1; while(l+11; if(dmm=lose) l=mm; else r=mm; he=qu