Codeforces 877E - Danil and a Part-time Job

发表于 分类于 Disqus：

链接

传送门

题意

给出一棵有\(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;
}
相关文章