当前位置 博文首页 > correct：NOI 2015 软件包管理器（树链剖分）
题目链接
中文题，不写题目描述了，大致意思就是，在安装和卸载程序的时候，会有依赖项，假设 A A A依赖于 B B B，那么安装 A A A之前必须先安装 B B B，同理，卸载 B B B之前必须卸载 A A A，问每次安装或卸载程序，有多少个安装包的状态被改变了。
当然，可以暴力求解，但是数据量不允许。
首先明确这是一个树的模型，（题中说了每个程序仅依赖于一个），但是可能会有一个依赖链，即 C C C依赖 B B B， B B B依赖于 A A A，而最终都会依赖到 0 0 0号节点（题中说的），因此安装的过程相当于求从这个节点到 0 0 0号节点的路径上有多少个未被安装的。
而卸载的过程，则是求解以这个点未根的子树上，有多少个点被安装了。
OK，可以通过树剖，讲树上的路径转换为连续的区间，然后用线段树去维护每一个区间的信息即可。由于本文不是讲树剖的，因此不多赘述。这里仅提供一个树链剖分的讲解blog 树链剖分
树剖后，可以很方便的处理这两个问题，对于安装过程而言，就是求两个点之间的路径上未安装的个数的和，用线段树维护每一个区间内的未被安装的个数即可，然后讲两个点不断上升至到达同一重链上，过程中还要计算每一条重链上的和，累加即可。
对于卸载过程而言，因为一个点的子树上的所有的点的时间戳都是连续的，因此也直接转换为对线段树上的一段连续区间进行操作。
注意： 更新操作比较特殊，不再是累加，而是直接覆盖，例如对区间 [ 1 , 5 ] [1,5] [1,5]先进行操作，全部安装，下次操作它的子区间，是直接将子区间用新的标记覆盖了，因此线段树中标记下传需要一点小改动。
因为我用线段树维护的是未安装的数量，因此卸载过程需要减法，当然也可以换成维护已安装的数量，甚至两个都维护。
直接看代码吧：
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof a)
using namespace std;
const int N = 100100;
int head[N], nex[N * 2], to[N * 2], cnt;
void add(int a, int b) {
++cnt;
to[cnt] = b;
nex[cnt] = head[a];
head[a] = cnt;
}
int fa[N], depth[N], son[N], siz[N];
void dfs1(int x, int dep) {
depth[x] = dep;
siz[x] = 1;
int max_size = -1;
for (int i = head[x]; ~i; i = nex[i]) {
int y = to[i];
if (y == fa[x])continue;
if (!depth[y]) {
fa[y] = x;
dfs1(y, dep + 1);
siz[x] += siz[y];
if (max_size == -1 | max_size < siz[y]) {
max_size = siz[y];
son[x] = y;
}
}
}
}
int dfn[N], rk[N], num, top[N];
void dfs2(int x, int tp) {
dfn[x] = ++num;
rk[num] = x;
top[x] = tp;
if (son[x] == -1)return;
dfs2(son[x], tp);
for (int i = head[x]; ~i; i = nex[i]) {
int y = to[i];
if (y != son[x] && y != fa[x]) {
dfs2(y, y);
}
}
}
void init() {
mem(head, -1), mem(nex, -1), cnt = 0;
num = 0, mem(dfn, -1), mem(rk, -1), mem(top, -1);
mem(fa, -1), mem(depth, 0), mem(siz, 0), mem(son, -1);
}
struct p {
int l, r, sum, length, lazy;
};
typedef struct SegementTree {
p c[N * 4];
void build(int l, int r, int k) {
c[k].l = l;
c[k].r = r;
c[k].sum = 0;
c[k].length = 0;
c[k].lazy = 0;
if (l == r) {
c[k].length = 1;
c[k].sum = 1;
return;
}
int mid = (l + r) >> 1;
build(l, mid, k << 1);
build(mid + 1, r, k << 1 | 1);
c[k].length = c[k << 1].length + c[k << 1 | 1].length;
c[k].sum = c[k << 1].sum + c[k << 1 | 1].sum;
}
void down(int k) {// 标记下传
if (c[k].lazy) {
int lz = c[k].lazy;
c[k << 1].sum = lz == -1 ? c[k << 1].length : 0;
c[k << 1 | 1].sum = lz == -1 ? c[k << 1 | 1].length : 0;
c[k << 1].lazy = c[k << 1 | 1].lazy = c[k].lazy;
c[k].lazy = 0;
}
}
int query(int l, int r, int k) {
if (l <= c[k].l && r >= c[k]
