0%

[NOI2015] 软件包管理器

题目

题目链接

题目大意: 维护 $n$ 个软件的安装和卸载. 除了 0 号软件外每个软件有一个前置软件, 每安装一个软件需要安装所有前置软件, 每卸载一个软件需要卸载所有后置软件, 问每次操作涉及到的软件个数并执行操作. $1 \le n, q \le 10^5$.

思路

不难发现依赖关系构成了一棵树. 安装是对从当前节点到根节点进行操作, 卸载是对子树进行操作.

然后直接树剖就可以了. 线段树维护区间中 1 的个数.

这里编号是从 0 开始的, 线段树的标记问题也要处理一下, 当 tag[x] = 0 时按照 if (tag[x]) 的写法写就会出问题.

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;
typedef unsigned long long uLL;

struct Node {
int l, r, v, tag;
} t[400010];

std::vector<int> g[100010];
int top[100010], dfn[100010], dep[100010], fa[100010], son[100010], siz[100010];
int n, q, tot;
char op[15];

inline int lson(int x) { return x << 1; }
inline int rson(int x) { return x << 1 | 1; }

void buildTree(int x, int l, int r) {
t[x].l = l, t[x].r = r;
if (l == r) return ;
int mid = (l + r) >> 1;
buildTree(lson(x), l, mid),buildTree(rson(x), mid + 1, r);
}

void pushDown(int x) {
if (t[x].tag) {
t[lson(x)].tag = t[rson(x)].tag = t[x].tag;
t[lson(x)].v = (t[x].tag - 1) * (t[lson(x)].r - t[lson(x)].l + 1);
t[rson(x)].v = (t[x].tag - 1) * (t[rson(x)].r - t[rson(x)].l + 1);
t[x].tag = 0;
}
}

int query(int x, int l, int r) {
if (t[x].l >= l && t[x].r <= r) return t[x].v;
pushDown(x);
int s = 0, mid = (t[x].l + t[x].r) >> 1;
if (l <= mid) s += query(lson(x), l, r);
if (r > mid) s += query(rson(x), l, r);
return s;
}

void modify(int x, int l, int r, int d) {
if (t[x].l >= l && t[x].r <= r) {
t[x].tag = d + 1;
t[x].v = d * (t[x].r - t[x].l + 1);
return ;
}
pushDown(x);
int mid = (t[x].l + t[x].r) >> 1;
if (l <= mid) modify(lson(x), l, r, d);
if (r > mid) modify(rson(x), l, r, d);
t[x].v = t[lson(x)].v + t[rson(x)].v;
}

void dfs1(int x, int p) {
dep[x] = dep[p] + 1;
siz[x] = 1;
fa[x] = p;
for (auto i : g[x]) {
dfs1(i, x);
siz[x] += siz[i];
if (siz[i] > siz[son[x]]) son[x] = i;
}
}

void dfs2(int x, int tp) {
top[x] = tp;
dfn[x] = ++tot;
if (son[x]) {
dfs2(son[x], tp);
for (auto i : g[x]) {
if (i != son[x]) {
dfs2(i, i);
}
}
}
}

int ask(int u, int v) {
int s = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
int sum = (dfn[u] - dfn[top[u]] + 1) - query(1, dfn[top[u]], dfn[u]);
s += sum;
modify(1, dfn[top[u]], dfn[u], 1);
u = fa[top[u]];
}
if (dfn[u] > dfn[v]) std::swap(u, v);
int sum = (dfn[v] - dfn[u] + 1) - query(1, dfn[u], dfn[v]);
s += sum;
modify(1, dfn[u], dfn[v], 1);
return s;
}

int main() {
read(n);
for (int i = 2, x; i <= n; ++i) {
read(x);
++x;
g[x].push_back(i);
}
dfs1(1, 0);
dfs2(1, 1);
buildTree(1, 1, n);
read(q);
while (q--) {
int x;
scanf("%s", op + 1);
read(x);
++x;
if (op[1] == 'i') {
printf("%d\n", ask(x, 1));
} else {
printf("%d\n", query(1, dfn[x], dfn[x] + siz[x] - 1));
modify(1, dfn[x], dfn[x] + siz[x] - 1, 0);
}
}
return 0;
}