Problem’s Website
- NOI_2015软件包管理器
Solution
- 一道经典的树链剖分题，我们把有依赖关系的软件包用树联系起来，对其进行树剖，设1为已安装，0为未安装，赋值前统计1的个数，赋值后取差值即可。
- 这道题正解是线段树维护，但本菜鸡为了复习ODT，于是就开O2写了个ODT过了这道题。。。
- 这道题用ODT维护和线段树差不多，核心就是assign函数，也是ODT复杂度的保证。
Code
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
const int Maxn = 2e5 + 10;
inline int sc() {
int xx = 0, ff = 1; char cch = gc;
while(!isdigit(cch)) {
if(cch == '-') ff = -1; cch = gc;
}
while(isdigit(cch)) {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
inline void out(int x) {
if(x < 0) pc('-'), x = -x;
if(x >= 10)
out(x / 10);
pc(x % 10 + '0');
}
inline int aabs(int x) {
return x > 0 ? x : -x;
}
struct ODT {
int l, r;
mutable int v;
bool operator < (const ODT &x) const {
return l < x.l;
}
ODT(int L, int R = -1, int V = 0) : l(L), r(R), v(V) {}
};
std :: set <ODT> s;
Int split(int pos) {
Int it = s.lower_bound(ODT(pos));
if(it != s.end() && it->l == pos) return it;
--it;
int L = it->l, R = it->r, V = it->v;
s.erase(it), s.insert(ODT(L, pos - 1, V));
return s.insert(ODT(pos, R, V)).first;
}
int assign(int l, int r, int v) {
Int it2 = split(r + 1), it1 = split(l);
int sum = 0, SUM = v * (r - l + 1);
for(Int it = it1; it != it2; ++it)
sum += it->v * (it->r - it->l + 1);
s.erase(it1, it2), s.insert(ODT(l, r, v));
return aabs(SUM - sum);
}
struct node {
int next, to;
}t[Maxn << 1];
int n, cnt, m;
int head[Maxn];
int dep[Maxn], fa[Maxn], siz[Maxn], id[Maxn], son[Maxn], top[Maxn];
inline void ADD(int from, int to) {
t[++cnt].next = head[from];
t[cnt].to = to;
head[from] = cnt;
}
inline void dfs1(int now, int Fa, int Dep) {
dep[now] = Dep;
fa[now] = Fa;
siz[now] = 1;
for(re int i = head[now]; i; i = t[i].next) {
int to = t[i].to;
if(to == Fa) continue;
dfs1(to, now, Dep + 1);
siz[now] += siz[to];
if(siz[son[now]] < siz[to])
son[now] = to;
}
}
inline void dfs2(int now, int topf) {
id[now] = ++cnt;
// aa[cnt] = a[now];
top[now] = topf;
// std :: cerr << cnt << std :: endl;
if(!son[now]) return;
dfs2(son[now], topf);
for(re int i = head[now]; i; i = t[i].next) {
int to = t[i].to;
if(to == fa[now] || to == son[now]) continue;
dfs2(to, to);
}
}
inline int in(int x, int y) {
int res = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std :: swap(x, y);
res += assign(id[top[x]], id[x], 1);
x = fa[top[x]];
}
if(dep[x] > dep[y]) std :: swap(x, y);
res += assign(id[x], id[y], 1);
return res;
}
inline int un(int x) {
return assign(id[x], id[x] + siz[x] - 1, 0);
}
int main() {
n = sc();
s.insert(ODT(1, n + 1, 0));
for(re int i = 2; i <= n; ++i) {
int x = sc();
++x;
ADD(x, i);
}
cnt = 0;
dfs1(1, 0, 1);
dfs2(1, 1);
m = sc();
while(m--) {
char c[10];
std :: cin >> c;
if(c[0] == 'i') {
int x = sc();
++x;
out(in(x, 1)), pc('\n');
}
else {
int x = sc();
++x;
out(un(x)), pc('\n');
}
}
return 0;
}
// Coded by dy.
rp++