Broccoli or Cauliflower [RUPC2018 Day3 E]

前提知識

• オイラーツアー
• 遅延評価セグメントツリー（区間xor1区間総和）

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2753110

部分木にまつわるクエリなので、オイラーツアーとセグメントツリーを使ういつものやつかなと想像する。
クエリの内容を考えてみると、これは値の反転をしていることになる。
そして、Gの数やWの数を数えるのは、全体の総和を取っている感じになるので、区間xor1（区間反転）区間総和の遅延評価セグメントツリーがあれば解けると言える。
この実装が一番難しいのだが、遅延評価の情報として「反転させるか」という情報をもたせる。
もし、反転させるならば、dat[k] = (r-l) - dat[k]のように区間総和を反転させる。

template<class V, int NV> struct LazySegTree { // [L,R)
    vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
    void update(int a, int b, V v, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return;
        if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); } else {
        update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r);
        dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);}}
    V get(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return def;
        if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
        auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y);}
    void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); }
    V get(int a, int b) { return get(a, b, 0, 0, NV); }
    // ---- Template ---------------------------------------------------------------------------------
    
    const V def = 0, ldef = 0;
    V comp(V l, V r) { return l + r; }
    void setLazy(int i, V v) { lazy[i] ^= v; }
    void push(int k, int l, int r) {
        if(lazy[k]) dat[k] = (r - l) - dat[k];
        if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); }
        lazy[k] = ldef;
    }
};

これがうまく実装できれば、あとは答えるだけ。

int N, Q;
vector<int> E[101010];
LazySegTree<int, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
int L[401010], R[401010];
int idx = 0;
void euler(int cu, int pa = -1) { // [L[v],R[v])
    L[cu] = idx; idx++;
    for (int to : E[cu]) if (to != pa) euler(to, cu);
    R[cu] = idx;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 2, N + 1) {
        int p; cin >> p;
        int a = i - 1;
        int b = p - 1;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    euler(0);

    rep(i, 0, N) {
        char c; cin >> c;
        if (c == 'G') st.update(L[i], L[i] + 1, 1);
    }

    rep(q, 0, Q) {
        int v; cin >> v; v--;
        st.update(L[v], R[v], 1);

        int sm = st.get(0, N);

        if (N / 2 < sm) printf("broccoli\n");
        else printf("cauliflower\n");
    }
}