Skip to content

「NOI2015」软件包管理器

题解约 1.9 千字
# 洛谷 # LibreOJ # AcWing # 线段树 # 树链剖分 # NOI # 2015
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。

#题目描述

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 aa 依赖软件包 bb，那么安装软件包 aa 以前，必须先安装软件包 bb。同时，如果想要卸载软件包 bb，则必须卸载软件包 aa。

现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 00 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 00 号软件包不依赖任何一个软件包。且依赖关系不存在环（即不会存在 mm 个软件包 a1,a2,…,ama_1,a_2, \dots , a_m，对于 i<mi<m，aia_i 依赖 ai+1a_i+1，而 ama_m 依赖 a1a_1 的情况）。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。

注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 00。

#输入格式

第一行一个正整数 nn，表示软件包个数，从 00 开始编号。 第二行有 n−1n-1 个整数，第 ii 个表示 ii 号软件包依赖的软件包编号。 然后一行一个正整数 qq，表示操作个数，格式如下：

  • install x 表示安装 xx 号软件包
  • uninstall x 表示卸载 xx 号软件包

一开始所有软件包都是未安装的。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

#输出格式

输出 qq 行，每行一个整数，表示每次询问的答案。

#输入输出样例

样例输入 #1

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

样例输出 #1

3
1
3
2
3

样例解释 #1

一开始所有软件包都处于未安装状态。

安装 55 号软件包，需要安装 0,1,50,1,5 三个软件包。

之后安装 66 号软件包，只需要安装 66 号软件包。此时安装了 0,1,5,60,1,5,6 四个软件包。

卸载 11 号软件包需要卸载 1,5,61,5,6 三个软件包。此时只有 00 号软件包还处于安装状态。

之后安装 44 号软件包，需要安装 1,41,4 两个软件包。此时 0,1,40,1,4 处在安装状态。最后，卸载 00 号软件包会卸载所有的软件包。

样例输入 #2

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

样例输出 #2

1
3
2
1
3
1
1
1
0
1

#数据范围与约定

#思路

一道树链剖分模板题。

通过分析可得：每次执行安装操作时，把根节点到软件 XX 路径上的值设为 11 ；每次执行卸载操作时，把以 XX 为根节点的子树上的所有值设为 00 。

然后题目就转化为了区间和问题，操作前记录下线段树整体的和，操作后再记录一次，两者相减取绝对值即为安装状态被改变了的软件包的数量。

几点注意事项：

  1. 线段树区间覆盖的实现：在修改时将 += 改为 = 即可。
  2. 懒标记初值不要用 00 ，因为修改的时候会有 00 。
  3. 推荐从 11 开始编号，方便维护，避免因编号起始值不同带来的麻烦。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;

const int N = 100005;

int n, q, a, x;
std::string op;
std::vector<int> g[N];

// Heavy Path Decomposition
int cnt, id[N], fa[N], dep[N], son[N], siz[N], top[N];
void dfs1(int, int);
void dfs2(int, int);
void modify_path(int, int, int);
void modify_tree(int, int);

// Segment Tree
void pushup(int);
void pushdown(int);
void build(int, int, int);
void modify(int, int, int, int);
int query(int, int, int);

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> x;
        x++;
        g[x].push_back(i);
        g[i].push_back(x);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    build(1, 1, n);
    cin >> q;
    while (q--) {
        cin >> op >> x;
        x++;
        int before = query(1, 1, n);
        if (op == "install") {
            if (!query(1, id[x], id[x])) {
                modify_path(1, x, 1);
            }
        } else {
            if (query(1, id[x], id[x])) {
                modify_tree(x, 0);
            }
        }
        int after = query(1, 1, n);
        cout << std::abs(before - after) << endl;
    }
    return 0;
}

// === Heavy Path Decomposition ===

void dfs1(int u, int f) {
    dep[u] = dep[f] + 1;
    fa[u] = f;
    siz[u] = 1;
    for (int v : g[u]) {
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs2(int u, int t) {
    id[u] = ++cnt;
    top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int v : g[u]) {
        if (v == fa[u]) continue;
        if (v == son[u]) continue;
        dfs2(v, v);
    }
}

void modify_path(int u, int v, int d) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        modify(1, id[top[u]], id[u], d);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) std::swap(u, v);
    modify(1, id[v], id[u], d);
}

void modify_tree(int u, int d) {
    modify(1, id[u], id[u] + siz[u] - 1, d);
}

// === Segment Tree ===

struct node {
    int l, r, s, d;

    node()
        : l(0), r(0), s(0), d(-1) {}
    node(int _l, int _r)
        : l(_l), r(_r), s(0), d(-1) {}
} tr[N << 2];

inline void pushup(int u) {
    tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}

inline void pushdown(int u) {
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.d == -1) return;
    left.s = (left.r - left.l + 1) * root.d;
    left.d = root.d;
    right.s = (right.r - right.l + 1) * root.d;
    right.d = root.d;
    root.d = -1;
}

void build(int u, int l, int r) {
    tr[u] = node(l, r);
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int d) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].s = (tr[u].r - tr[u].l + 1) * d;
        tr[u].d = d;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= mid) modify(u << 1, l, r, d);
    if (r > mid) modify(u << 1 | 1, l, r, d);
    pushup(u);
}

int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].s;
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    pushdown(u);
    if (l <= mid) sum += query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}