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; }
|