软件包管理器

题面
思路:

依赖关系不存在环,说明这是一颗有向树,0为根节点(不依赖任何的软件包)。安装时是查询x到根路径上权值为0的节点个数,然后再将x到根路径上的节点权值全部变为1就行了。卸载时查询x的子树中有多少个权值为1的节点个数,然后再将x及其子树的所有节点全部变为0就行了。上述操作只需用树链剖分实现,把线段树改为01可区间修改的线段树就可以了。

代码:
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
153
154
155
156
157
// luogu-judger-enable-o2//原谅我不可饶恕的常数
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n,fa[maxn],size[maxn],son[maxn],id[maxn],dep[maxn],top[maxn],cnt,q;
vector<int>e[maxn];
struct node
{
int val,tag;
}tr[maxn << 2];
void dfs1(int x)
{
dep[x] = dep[fa[x]] + 1;
size[x] = 1;int maxson = -1;
for(int i = 0 ; i < e[x].size() ; ++ i)
{
int v = e[x][i];
fa[v] = x;
dfs1(v);
size[x] += size[v];
if(size[v] > maxson)maxson = size[v],son[x] = v;
}
}
void dfs2(int x,int topf)
{
top[x] = topf;
id[x] = ++cnt;
if(!son[x])return;
dfs2(son[x],topf);
for(int i = 0 ; i < e[x].size() ; ++ i)
{
int v = e[x][i];
if(v == son[x])continue;
dfs2(v,v);
}
}
void update(int root)
{
tr[root].val = (tr[root << 1].val + tr[root << 1 | 1].val);
}
void build(int root,int l,int r)
{
tr[root].tag = -1;
if(l == r)return;
int mid = l + r >> 1;
build(root << 1,l,mid);
build(root << 1 | 1,mid + 1,r);
}
void push_down(int root,int l,int r)
{
if(tr[root].tag == 0){
tr[root << 1].val = 0;
tr[root << 1].tag = 0;
tr[root << 1 | 1].val = 0;
tr[root << 1 | 1].tag = 0;
}
if(tr[root].tag == 1){
int mid = l + r >> 1;
tr[root << 1].val = mid - l + 1;
tr[root << 1].tag = 1;
tr[root << 1 | 1].val = r - mid;
tr[root << 1 | 1].tag = 1;
}
tr[root].tag = -1;
}
int query0(int root,int l,int r,int L,int R)
{
int ans = 0;
if(l >= L and r <= R)return r - l + 1 - tr[root].val;
int mid = l + r >> 1;
push_down(root,l,r);
if(L <= mid)ans += query0(root << 1,l,mid,L,R);
if(R > mid)ans += query0(root << 1 | 1,mid + 1,r,L,R);
update(root);
return ans;
}
int query1(int root,int l,int r,int L,int R)
{
int ans = 0;
if(l >= L and r <= R)return tr[root].val;
int mid = l + r >> 1;
push_down(root,l,r);
if(L <= mid)ans += query1(root << 1,l,mid,L,R);
if(R > mid)ans += query1(root << 1 | 1,mid + 1,r,L,R);
update(root);
return ans;
}
void change(int root,int l,int r,int L,int R,int opt)
{
if(l >= L and r <= R){
if(opt == 0)
{
tr[root].val = 0;
tr[root].tag = 0;
}
if(opt == 1)
{
tr[root].val = r - l + 1;
tr[root].tag = 1;
}
return;
}
int mid = l + r >> 1;
push_down(root,l,r);
if(L <= mid)change(root << 1,l,mid,L,R,opt);
if(R > mid)change(root << 1 | 1,mid + 1,r,L,R,opt);
update(root);
}
int road_ask(int x)
{
int ans = 0;
while(top[x] != top[0])
{
ans += query0(1,1,n,id[top[x]],id[x]);
x = fa[top[x]];
}
ans += query0(1,1,n,id[0],id[x]);
return ans;
}
void Install(int x)
{
while(top[x] != top[0])
{
change(1,1,n,id[top[x]],id[x],1);
x = fa[top[x]];
}
change(1,1,n,id[0],id[x],1);
}
int son_ask(int x)
{
return query1(1,1,n,id[x],id[x] + size[x] - 1);
}
void Uninstall(int x)
{
change(1,1,n,id[x],id[x] + size[x] - 1,0);
}
signed main()
{
cin >> n;
for(int i = 1,x ; i < n ; ++ i)
{
cin >> x;
e[x].push_back(i);
}
dfs1(0);
dfs2(0,0);
build(1,1,n);
cin >> q;
while(q--)
{
string opt;int x;
cin >> opt >> x;
if(opt == "install")cout << road_ask(x) << endl,Install(x);
else cout << son_ask(x) << endl,Uninstall(x);
}
return 0;
}