Codeforces 877E Danil and a Part-time Job（dfs序 + 线段树）

#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)for (int i(a); i <= (b); ++i)
#define dec(i, a, b)for (int i(a); i >= (b); --i)
#define lsi << 1
#definersi << 1 | 1
#define lsonls, L, mid
#definersonrs, mid + 1, Rconst int N = 2e5 + 10;struct node{
int s[2];
int len;
} t[N * 3];int in[N], out[N], dc[N * 3], dt[N * 3], f[N], a[N];
int n, q, ti;vector <int> v[N];void dfs(int x){
in[x] = ++ti;
f[ti] = x;
for (auto u : v[x]) dfs(u);
out[x] = ti;
}node update(node x, node y){
node ans;
ans.len = x.len + y.len;
rep(i, 0, 1) ans.s[i] = x.s[i] + y.s[i];
return ans;
}void build(int i, int L, int R){
if (L == R){
int z = a[f[L]];
t[i].len = t[i].s[z] = 1;
t[i].s[z ^ 1] = 0;
dc[i] = -1;
dt[i] = 0;
return ;
}int mid = (L + R) >> 1;
build(lson);
build(rson);
t[i] = update(t[ls], t[rs]);
dc[i] = -1;
dt[i] = 0;
}void cover(int i, int z){
dc[i] = z;
dt[i] = 0;
t[i].s[z] = t[i].len;
t[i].s[z ^ 1] = 0;
}void turn(int i, int z){
if (~z){
dc[i] ^= 1;
t[i].s[z] = 0;
t[i].s[z ^ 1] = t[i].len;
}else{
dt[i] ^= 1;
swap(t[i].s[0], t[i].s[1]);
}
}void pushdown(int i){
if (~dc[i]){
cover(ls, dc[i]);
cover(rs, dc[i]);
dc[i] = -1;
}if (dt[i]){
turn(ls, dc[ls]);
turn(rs, dc[rs]);
dt[i] = 0;
}
}void Turn(int i, int L, int R, int x, int y){
if (x <= L && R <= y){
turn(i, dc[i]);
return;
}pushdown(i);
int mid = (L + R) >> 1;
if (x <= mid) Turn(lson, x, y);
if (y > mid) Turn(rson, x, y);
t[i] = update(t[ls], t[rs]);
}int query(int i, int L, int R, int x, int y){
int ret = 0;
if (x <= L && R <= y) return t[i].s[1];
int mid = (L + R) >> 1;
pushdown(i);
if (x <= mid) ret += query(lson, x, y);
if (y > mid ) ret += query(rson, x, y);
return ret;
}int main(){scanf("%d", &n);
rep(i, 2, n){
int x;
scanf("%d", &x);
v[x].push_back(i);
}dfs(1);
rep(i, 1, n) scanf("%d", a + i);
build(1, 1, n);for (scanf("%d", &q); q--; ){
char op[10]; int x;
scanf("%s%d", op, &x);
if (op[0] == 'g') printf("%d\n", query(1, 1, n, in[x], out[x]));
else Turn(1, 1, n, in[x], out[x]);
}return 0;
}