树链剖分学习笔记

　　这里就不写具体实现了...只是为刚看懂什么是树链剖分的同学提供习题

　　其实树剖部分都差不多的，关键是线段树

　　可以把这里面5题A了大概就可以熟悉树链剖分了...

T1:LuoguP3384 【模板】树链剖分

　　都说了是模板，那就是模板咯...

　　考虑线段树实现区间加、区间和，又是线段树模板...

　　树剖跳的时候，因为要更新子树，然后这里更新的话直接idx[x]+sz[x]-1就可以了（因为这些编号是相连的）

　　取模不要漏！！！

  1 // luogu-judger-enable-o2
  2 #include<cstdio>
  3 #include<queue>
  4 #include<iostream>
  5 #include<cstring>
  6 #define int long long
  7 using namespace std;
  8 inline int read(){
  9     int ans=0,f=1;char chr=getchar();
 10     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 11     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 12     return ans*f;
 13 }const int M=300005;
 14 int n,m,head[M<<1],ver[M<<1],nxt[M<<1],tot,son[M],dep[M],sz[M],idx[M],fa[M],tp[M],root,ha,a[M],b[M],sum[M<<2],lz[M<<2],rk[M];
 15 inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
 16 void dfs1(int x,int f){
 17     sz[x]=1,fa[x]=f,dep[x]=dep[f]+1;
 18     for(int i=head[x];i;i=nxt[i]){
 19         if(ver[i]==f) continue;
 20         dfs1(ver[i],x);
 21         sz[x]+=sz[ver[i]];
 22         if(sz[ver[i]]>sz[son[x]]) son[x]=ver[i];
 23     }
 24 }int t;
 25 void dfs2(int x,int topf){
 26     tp[x]=topf;idx[x]=++t;a[t]=b[x];rk[t]=x;
 27     if(!son[x]) return;
 28     dfs2(son[x],topf);
 29     for(int i=head[x];i;i=nxt[i])
 30         if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
 31 }
 32 #define ls (i<<1)
 33 #define rs (i<<1|1)
 34 #define mid ((l+r)>>1)
 35 inline void Push_Up(int i){sum[i]=(sum[ls]+sum[rs]+ha)%ha;}
 36 inline void Push_Down(int i,int l,int r){
 37     if(!lz[i]) return;
 38     sum[ls]=(sum[ls]+lz[i]*(mid-l+1)%ha)%ha,sum[rs]=(sum[rs]+lz[i]*(r-mid)%ha)%ha;
 39     lz[ls]=(lz[ls]+lz[i])%ha,lz[rs]=(lz[rs]+lz[i])%ha,lz[i]=0;
 40 }
 41 void Build(int i,int l,int r){
 42     if(l==r){sum[i]=a[l];return;}
 43     Build(ls,l,mid),Build(rs,mid+1,r);
 44     Push_Up(i);
 45 }
 46 void Update(int i,int l,int r,int ql,int qr,int z){
 47     if(ql<=l&&r<=qr){sum[i]=((r-l+1)*z+sum[i])%ha;lz[i]=(lz[i]+z)%ha;return;}
 48     Push_Down(i,l,r);
 49     if(ql<=mid) Update(ls,l,mid,ql,qr,z);
 50     if(qr>mid)  Update(rs,mid+1,r,ql,qr,z);
 51     Push_Up(i);
 52 }
 53 int Query(int i,int l,int r,int ql,int qr){
 54     if(ql<=l&&r<=qr) return sum[i];
 55     Push_Down(i,l,r);int s=0;
 56     if(ql<=mid) s=(s+Query(ls,l,mid,ql,qr))%ha;
 57     if(qr>mid)  s=(s+Query(rs,mid+1,r,ql,qr))%ha;
 58     Push_Up(i);
 59     return s;
 60 }
 61 void Query_1(int x,int y,int val){
 62     while(tp[x]!=tp[y]){
 63         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
 64         Update(1,1,n,idx[tp[x]],idx[x],val);
 65         x=fa[tp[x]];
 66     }
 67     if(dep[x]>dep[y]) swap(x,y);
 68     Update(1,1,n,idx[x],idx[y],val);
 69 }
 70 void Query_2(int x,int y){
 71     int Ans=0;
 72     while(tp[x]!=tp[y]){
 73         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
 74         Ans=(Ans+Query(1,1,n,idx[tp[x]],idx[x]))%ha;
 75         x=fa[tp[x]];
 76     }if(dep[x]>dep[y]) swap(x,y);
 77     Ans=(Ans+Query(1,1,n,idx[x],idx[y]))%ha;
 78     printf("%lld\n",Ans);
 79 }
 80 void Query_3(int x,int y){Update(1,1,n,idx[x],idx[x]+sz[x]-1,y%ha);}
 81 void Query_4(int x){printf("%lld\n",Query(1,1,n,idx[x],idx[x]+sz[x]-1));}
 82 int Q_d(int i,int l,int r,int p){
 83     if(l==r)return sum[i];
 84     Push_Up(i);
 85     if(p<=mid) return Q_d(ls,l,mid,p);
 86     else return Q_d(rs,mid+1,r,p);
 87 }
 88 signed main(){
 89     n=read(),m=read(),root=read(),ha=read();
 90     for(int i=1;i<=n;++i) b[i]=read();
 91     for(int i=1,x,y,z;i<n;++i){x=read(),y=read(),add(x,y),add(y,x);}
 92     dfs1(root,0),dfs2(root,root),Build(1,1,n);
 93     while(m--){int opt=read(),x,y,z;
 94         if(opt==4)    x=read(),Query_4(x);
 95         else{x=read(),y=read();
 96             if(opt==3) Query_3(x,y%ha);
 97             else if(opt==2) Query_2(x,y);
 98             else z=read(),Query_1(x,y,z%ha);
 99         }
100     }return 0;
101 }

T2:LuoguP4114 Qtree1

　　单调修改+区间查询，线段树是板子不讲了

　　树剖部分：因为修改的是加边的时候的第k条边，就用到链式前向星的性质了...自己手推一下应该改哪条边即可

　　（我的代码线段树打的是区间修改还支持区间加的...主要是模板懒得改了，不影响树剖部分的阅读性）

 1 // luogu-judger-enable-o2
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstring>
 5 #define int long long
 6 using namespace std;
 7 inline int read(){
 8     int ans=0,f=1;char chr=getchar();
 9     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
11     return ans*f;
12 }const int M = 100005;char opt[10];
13 int n,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot,fa[M],dep[M],sz[M],b[M],a[M],son[M],idx[M],tp[M],mx[M<<2],lz1[M<<2],lz2[M<<2],rk[M],x,y,z;
14 inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;}
15 void dfs1(int x,int f){
16     dep[x]=dep[f]+1;sz[x]=1;fa[x]=f;
17     for(int i=head[x];i;i=nxt[i]){
18         if(ver[i]==f) continue;
19         b[ver[i]]=val[i],dfs1(ver[i],x),sz[x]+=sz[ver[i]];
20         if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
21     }
22 }int t;
23 void dfs2(int x,int topf){
24     tp[x]=topf;idx[x]=++t;a[t]=b[x];
25     if(!son[x]) return;
26     dfs2(son[x],topf);
27     for(int i=head[x];i;i=nxt[i])
28         if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
29 }
30 #define ls (i<<1)
31 #define rs (i<<1|1)
32 #define mid (l+r>>1)
33 inline void Push_Up(int i){mx[i]=max(mx[ls],mx[rs]);}
34 inline void Push_Down(int i){
35     if(lz1[i]!=-1)
36         mx[ls]=mx[rs]=lz1[ls]=lz1[rs]=lz1[i],lz2[ls]=lz2[rs]=0,lz1[i]=-1;
37     if(!lz2[i]) return;
38     lz2[ls]+=lz2[i],lz2[rs]+=lz2[i];
39     mx[ls]+=lz2[i],mx[rs]+=lz2[i],lz2[i]=0;
40 }
41 void Build(int i,int l,int r){lz1[i]=-1;
42     if(l==r){mx[i]=a[l];return;}
43     Build(ls,l,mid),Build(rs,mid+1,r);
44     Push_Up(i);
45 }
46 void Update_1(int i,int l,int r,int ql,int qr,int x){
47     if(ql<=l&&r<=qr){mx[i]=x;lz1[i]=x,lz2[i]=0;return;}
48     Push_Down(i);
49     if(ql<=mid) Update_1(ls,l,mid,ql,qr,x);
50     if(qr>mid)  Update_1(rs,mid+1,r,ql,qr,x);
51     Push_Up(i);
52 }
53 void Update_2(int i,int l,int r,int ql,int qr,int x){
54     if(ql<=l&&r<=qr){mx[i]+=x;lz2[i]+=x;return;}
55     Push_Down(i);
56     if(ql<=mid) Update_2(ls,l,mid,ql,qr,x);
57     if(qr>mid)  Update_2(rs,mid+1,r,ql,qr,x);
58     Push_Up(i);
59 }
60 int Query(int i,int l,int r,int ql,int qr){
61     if(ql<=l&&r<=qr) return mx[i];
62     int ans=0;Push_Down(i);
63     if(ql<=mid) ans=max(ans,Query(ls,l,mid,ql,qr));
64     if(qr>mid)  ans=max(ans,Query(rs,mid+1,r,ql,qr));
65     return Push_Up(i),ans;
66 }
67 inline void Change(int x,int y){if(dep[ver[2*x-1]]<dep[ver[2*x]]) x=ver[2*x];else x=ver[2*x-1];Update_1(1,1,n,idx[x],idx[x],y);}
68 inline void Max(int x,int y){
69     int maxn=0,t=0;
70     if(x==y) puts("0");
71     if(x==y) return;
72     while(tp[x]!=tp[y]){
73         if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
74         t=Query(1,1,n,idx[tp[x]],idx[x]);
75         maxn=max(maxn,t);
76         x=fa[tp[x]]; 
77     }if(dep[x]>dep[y]) swap(x,y);
78     t=Query(1,1,n,idx[x]+1,idx[y]);maxn=max(t,maxn);
79     printf("%lld\n",maxn);
80 }
81 signed main(){
82     n=read();
83     for(int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
84     dfs1(1,0);dfs2(1,1);Build(1,1,n);
85     while(1){
86         scanf("%s",opt);
87         if(opt[1]=='O') return 0;
88         if(opt[1]=='H')x=read(),y=read(),Change(x,y);
89         else x=read(),y=read(),Max(x,y);
90     }
91     return 0;
92 }

T3:LuoguP4315 月下“毛景树”

　　知道为什么上一题要写区间加了吗...因为我是先做这题才做上面那题的!!!

　　难点是线段树，开两个lazy_tag(lz1,lz2),lz1记录区间覆盖,lz2记录区间加，更新顺序很重要，不过这是线段树部分注意的，这里既然是江树剖，那就不具体讲实现线段树了

树链剖分学习笔记

全站热榜