Online Judge：Luogu-P2146
Label：树链剖分，线段树区间覆盖
题目大意
\(n\)个软件包（编号0~n-1），他们之间的依赖关系用一棵含\(n-1\)条边的树来描述。一共两种操作：
install x：表示安装软件包xuninstall x：表示卸载软件包x
安装\(x\)时，必须得先安装x到根节点路径上所有的软件包；而卸载\(x\)时，必须得先卸载x子树中所有已经安装的软件包。对于每个操作，输出该操作前后，安装状态产生变化的节点的数量。
对于100%的数据，\(n,q<=100000\)
输入
输入文件的第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。
随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。
接下来一行包含1个整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种：
install x：表示安装软件包x
uninstall x：表示卸载软件包x
你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。
对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。
输出
输出文件包括q行。
输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。
样例
Input#1
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
Output#1
3
1
3
2
3
题解
将这两种操作对应到树上。
1.安装时：
将x到根节点的路径上所有点的安装状态赋值为已安装：1
2.卸载时：
将x子树内的点的安装状态赋值为未安装：0
发现两个操作都需要对一段连续区间进行赋值，注意不是修改，不过都可以利用线段树完成，至于线段树上区间的赋值和修改的具体差别在文末具体bb阐述。
第一个操作可以利用树链剖分跳重链，在O\((log^2N)\)的时间内完成跳跃以及修改一条链上的点的状态。
第二个操作，直接根据dfs序，对子树对应的区间进行区间赋值即可，单次操作的复杂度是\(O(logN)\)。
综上整个算法的时间复杂度为\(O(q \cdot log^2N)\)。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
struct edge{
int to,nxt;
}e[N];
int head[N],cnt;
inline void link(int u,int v){e[++cnt]=(edge){v,head[u]};head[u]=cnt;}
struct node{
int l,r,w,lazy;
}b[N<<2];
void build(int o,int l,int r){
b[o].l=l,b[o].r=r,b[o].lazy=-1;
if(l==r)return;
int mid=l+r>>1;
build(o<<1,l,mid),build(o<<1|1,mid+1,r);
}
void down(int o){
int g=b[o].lazy;
if(g==-1)return;
b[o<<1].w=(b[o<<1].r-b[o<<1].l+1)*g;
b[o<<1|1].w=(b[o<<1|1].r-b[o<<1|1].l+1)*g;
b[o<<1].lazy=b[o<<1|1].lazy=g;
b[o].lazy=-1;
}
void update(int o,int l,int r,int d){
if(b[o].l==l&&b[o].r==r){
b[o].w=(b[o].r-b[o].l+1)*d;
b[o].lazy=d;
return;
}
down(o);
int mid=b[o].l+b[o].r>>1;
if(r<=mid)update(o<<1,l,r,d);
else if(l>=mid+1)update(o<<1|1,l,r,d);
else{
update(o<<1,l,mid,d);update(o<<1|1,mid+1,r,d);
}
b[o].w=b[o<<1].w+b[o<<1|1].w;
}
int n,q;
int sz[N],dep[N],fa[N],top[N],son[N];
int li[N],ri[N],tot;
void predfs(int x,int f){
sz[x]=1;fa[x]=f;dep[x]=dep[f]+1;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
predfs(y,x);
sz[x]+=sz[y];
if(!son[x]||sz[y]>sz[son[x]])son[x]=y;
}
}
void redfs(int x,int tp){
top[x]=tp;li[x]=++tot;
if(son[x])redfs(son[x],tp);
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
if(y!=son[x])redfs(y,y);
}
ri[x]=tot;
}
void boom(int x,int y,int d){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,li[top[x]],li[x],d);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,li[x],li[y],d);
}
int main(){
n=read();
for(int i=2,u;i<=n;i++){
u=read();u++;
link(u,i);
}
predfs(1,0);redfs(1,1);
build(1,1,n);
q=read();
while(q--){
char op[13];scanf("%s",op);
int x=read(),base=b[1].w;
x++;
if(op[0]=='i'){
boom(1,x,1);
printf("%d\n",b[1].w-base);
}
else{
update(1,li[x],ri[x],0);
printf("%d\n",base-b[1].w);
}
}
}
End
借这道题整理一下几个常见问题及模板：
一、树链剖分
part1
树剖五件套：\(sz[]，son[]，fa[]，dep[]，top[]\)（分别对应子树大小，重儿子编号，父亲节点编号，深度，所属重链的顶端节点编号）
注意每个点必落在一条重链上，当只有一个点时，链退化成点，那个唯一的点，就是该条重链的top
part2
实现上主要分三个部分
predfs(root);//主要处理sz,son,fa,dep这四个数组
redfs(root,root);//主要处理top，题目需要时处理li[],ri[](dfs序)
calc(u,v);//统计路径(u,v)上的值、或者是对路径(u,v)进行修改
这里有一个细节，处理dfs序的时候必须得在\(redfs\)时进行，因为我们得保证一条重链上的\(li[]\)是连续的，这样才能映射到线段树上，对连续的一段链进行区间修改。当然，这样处理dfs序仍然能表示一个节点的子树->\([li[x],ri[x]]\)。
下面给出三个部分的模板代码
predfs
void predfs(int x,int f){
sz[x]=1;fa[x]=f;dep[x]=dep[f]+1;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;
predfs(y,x);
sz[x]+=sz[y];
if(!son[x]||sz[y]>sz[son[x]])son[x]=y;
}
}
redfs
void redfs(int x,int tp){
top[x]=tp;li[x]=++tot;
if(son[x])redfs(son[x],tp);
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to;if(y!=son[x])redfs(y,y);
}
ri[x]=tot;
}
calc
不同的题目，主要的变化就在第三部分，下面是几个常见问题的板子
1.求LCA
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
2.查询、修改一段路径
void boom(int x,int y,int d){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,li[top[x]],li[x],d);//修改时：ans+=query();
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,li[x],li[y],d);//修改时：ans+=query();
}
part3
安利一篇树剖的blog。
二、树状数组、线段树常见操作
Ⅰ.树状数组
相关blog：树状数组（含进阶版）
普通的树状数组支持：
0.单点修改+单点查询（普通数组就可以了2333）
1.单点更新+区间求和
2.区间更新+单点求值（利用差分）
3.单点更新+求前缀的最值（必须满足修改的值呈现单调性）
Ⅱ.线段树
相关操作比较多就不一一阐述了。这里区分一下本题中覆盖和修改(可理解为增加某个值)的操作。
part1：懒标记、节点的不同意义
覆盖操作和修改操作都需要打一个懒标记，但意义和用法有所不同。
对于更为常见的修改操作，\(lazy\)用来给儿子下传需要增加的累计值。节点\(o\)表示\([b[o].l,b[o].r]\)这整个区间的整合信息；
而对于覆盖操作，\(lazy\)用来标记该给这个区间赋的值，它与之前这棵树长什么样没有关系。对于非叶子节点的节点\(o\)来说它本身没有具体含义。
part2：具体实现
我们知道，在普通的区间修改操作时：
build：一开始建树时\(lazy\)就赋值为0，表示需要下传给儿子的累计值为0；
update：对于区间\([ql,qr]\)的修改操作，将被包含的节点的值\(w\)增加某个值，懒标记\(lazy\)增加某个值（具体操作视问题而定）；
down：对于某节点\(o\)的下传操作，将其左右儿子的\(w\)增加某个值，懒标记\(lazy\)增加某个值。
而对于区间覆盖来说，如果一开始建树时不能直接赋值为0(假如有某个赋值为0的操作，那就重了)，我们可以将其赋值为一个接下来操作中不会覆盖到的值，举个例子：假如你只对区间覆盖一个自然数，那么你就可以将\(lazy\)初始赋值为-1。而接下来对应操作中也不应该是增加，而是赋值。
part3：同时包含区间覆盖+区间修改的问题
可以参考这篇blog.
其实本质不变，开两个标记，根据情况分类讨论一下即可。