Codeforces 877E - Danil and a Part-Time Job

链接

传送门

题意

给出一棵有$n(1 \leq n \leq 200000)$个结点的有根树,每个结点上有一个灯,初始状态已知,有两种操作:

  • pow v:把以$v$为根的子树的结点上的灯状态反转;
  • get v:查询$v$为根的子树上有多少开着的灯。

对于每个get v输出查询结果,操作总次数为$q(1 \leq q \leq 200000)$。

思路

dfs对结点重新编号,使每个子树编号连续。这样,pow v是对区间进行反转,get v是求区间和,可以用线段树进行维护。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 200010;
const int maxnode = maxn << 2;
char s[5];
int n, n_, id;
int a[maxn];
int l[maxn], r[maxn];
int inv[maxnode];
int sumv[maxnode];
vector<int> g[maxn];
void maintain(int o, int L, int R) {
int lc = o * 2, rc = o * 2 + 1;
if(R > L) {
sumv[o] = sumv[lc] + sumv[rc];
}
if (inv[o]) {
sumv[o] = R - L + 1 - sumv[o];
if (L == R) {
inv[o] = 0;
}
}
}
void pushdown(int o) {
int lc = o * 2, rc= o * 2 + 1;
if (inv[o]) {
inv[lc] ^= 1;
inv[rc] ^= 1;
inv[o] = 0;
}
}
void update(int l, int r, int o = 1, int L = 1, int R = n_) {
int lc = o * 2, rc = o * 2 + 1;
if(l <= L && r >= R) {
inv[o] ^= 1;
} else {
pushdown(o);
int M = L + (R - L) / 2;
if(l <= M) update(l, r, lc, L, M);
else maintain(lc, L, M);
if(r > M) update(l, r, rc, M + 1, R);
else maintain(rc, M + 1, R);
}
maintain(o, L, R);
}
int query(int l, int r, int o = 1, int L = 1, int R = n_) {
int lc = o * 2, rc = o * 2 + 1;
maintain(o, L, R);
if(l <= L && r >= R) {
return sumv[o];
}
pushdown(o);
int M = L + (R - L) / 2;
int lsum = 0, rsum = 0;
if(l <= M) lsum = query(l, r, lc, L, M);
else maintain(lc, L, M);
if(r > M) rsum = query(l, r, rc, M+1, R);
else maintain(rc, M+1, R);
return lsum + rsum;
}
void dfs(int u) {
a[u] = ++id;
l[u] = id;
for (int v: g[u]) {
dfs(v);
}
r[u] = id;
}
int main() {
scanf("%d", &n);
for (int i = 2, x; i <= n; ++i) {
scanf("%d", &x);
g[x].push_back(i);
}
dfs(1);
n_ = 1;
while (n_ < n) {
n_ <<= 1;
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &sumv[n_ - 1 + a[i]]);
}
for (int i = n_ - 1; i >= 1; --i) {
sumv[i] = sumv[i * 2] + sumv[i * 2 + 1];
}
int q, v;
scanf("%d", &q);
while (q--) {
scanf("%s%d", s, &v);
if (s[0] == 'g') {
printf("%d\n", query(l[v], r[v]));
} else {
update(l[v], r[v]);
}
}
return 0;
}

支付宝扫码领红包