AOJ 2871 ブロッコリー？カリフラワー？ (RUPC 2018 day3-E)

オイラーツアー第三弾！
RUPC 2018 で見たばかりの問題でもある。

問題へのリンク

問題概要

頂点 1 を根とする頂点数 N の根付き木が与えられる。初期状態で各頂点に G または W の属性が割り振られている。以下の Q 個のクエリに答えよ:

• v: 頂点 v を根とする部分木の「G」と「W」を入れ替えたのち、「G」を「W」のうちのどちらがより多くなっているかを判定せよ

制約

• 1 <= N, Q <= 10⁵

考えたこと

根付き木の部分木に関する問題だからいかにもオイラーツアーっぽい。オイラーツアー上では、「部分木に対する操作」は「区間に対する操作」に対応するし、「部分木に関する値」は「区間についての値」に対応する。そうすると遅延評価セグメントツリーで解けそうである。

• セグツリーのノード: (Gの個数, Wの個数)
• セグツリーの遅延評価: 反転するかしないか

という感じでできそう。

• 反転の遅延フラグの更新: 反転フラグの真理値を入れ替え
• 具体的な反転操作: (G の個数, W の個数) の swap
• 区間の G の個数、W の個数: BIT 的な感じ

#include <iostream>
#include <vector>
using namespace std;

typedef pair<int,int> pint;
template<class Monoid, class Action> struct SegTree {
    int size_seg = 1;
    vector<Monoid> val;
    vector<Action> delay;
    Monoid UNITY_MONOID = pint(0, 0); // to be set
    Action UNITY_ACTION = 0;                    // to be set
    
    SegTree(int n = 1) { init(n); }
    SegTree(int n, const Monoid &init_monoid, const Action &init_action) { init(n, init_monoid, init_action); }
    
    void init(int n = 1) {
        size_seg = 1;
        while (size_seg < n) size_seg <<= 1;
        val.resize(size_seg * 2 - 1); delay.resize(size_seg * 2 - 1);
        for (int i = 0; i < size_seg * 2 - 1; ++i) {
            val[i] = UNITY_MONOID;
            delay[i] = UNITY_ACTION;
        }
    }

    inline void init_set(int a, const Monoid &x) {
        a += size_seg - 1;
        val[a] = x;
    }
    
    inline void init_tree(int k = 0, int l = 0, int r = -1) {
        if (r == -1) r = size_seg;
        if (r - l > 1) {
            init_tree(k*2+1, l, (l+r)/2);
            init_tree(k*2+2, (l+r)/2, r);
            val[k] = merge(val[k*2+1], val[k*2+2]);
        }
    }

    inline Monoid merge(const Monoid &x, const Monoid &y) {
        return pint(x.first + y.first, x.second + y.second);
    }
    
    inline void add(Action &d, const Action &e) {
        if (e) d = 1 - d;
    }
    
    inline void reflect(Monoid &x, const Action &d, int l, int r) {
        if (d) swap(x.first, x.second);
    }
    
    inline void redelay(int k, int l, int r) {
        reflect(val[k], delay[k], l, r);
        if (k < size_seg-1) {
            add(delay[k*2+1], delay[k]);
            add(delay[k*2+2], delay[k]);
        }
        delay[k] = UNITY_ACTION;
    }
    
    inline void renode(int k, int l, int r) {
        val[k] = merge(val[k*2+1], val[k*2+2]);
    }
    
    inline void set(int a, int b, Action x, int k = 0, int l = 0, int r = -1) {
        if (r == -1) r = size_seg;
        if (a <= l && r <= b) {                 // included
            add(delay[k], x);
            redelay(k, l, r);
        }
        else if (a < r && l < b) {              // intersected
            redelay(k, l, r);
            set(a, b, x, k*2+1, l, (l+r)/2);
            set(a, b, x, k*2+2, (l+r)/2, r);
            renode(k, l, r);
        }
        else {                                  // no-intersected
            redelay(k, l, r);
        }
    }
    
    inline Monoid get(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r == -1) r = size_seg;
        redelay(k, l, r);
        if (a <= l && r <= b) {                 // included
            return val[k];
        }
        else if (a < r && l < b) {              // intersected
            Monoid t1 = get(a, b, k*2+1, l, (l+r)/2);
            Monoid t2 = get(a, b, k*2+2, (l+r)/2, r);
            renode(k, l, r);
            return merge(t1, t2);
        }
        else {                                  // no-intersected
            return UNITY_MONOID;
        }
    }
    inline Monoid operator [] (int i) {return get(i, i+1);}
    
    void print() {
        long long t = 2;
        for (int i = 0; i < size_seg*2-1; ++i) {
            cout << make_pair(val[i], delay[i]) << ",";
            if (i == t-2) {cout << endl; t *= 2;}
        }
        cout << endl;
        for (int i = 0; i < size_seg; ++i) {
            cout << get(i, i+1) << ", ";
        }
        cout << endl << endl;
    }
};

typedef vector<vector<int> > Graph;

int N, Q;
vector<int> isG;
Graph tree;

struct EulerTour {
    // main results
    vector<int> depth;
    vector<int> node; // the node-number of i-th element of Euler-tour
    vector<int> vf, ve; // the index of Euler-tour of node v
    
    // sub results
  SegTree<pint, int> seg;
    
    EulerTour(const Graph &tree) { init(tree); }
    void init(const Graph &tree) {
        int V = (int)tree.size();
        depth.resize(V*2-1); node.resize(V*2-1); vf.resize(V); ve.resize(V);
        seg.init(V*2-1);
        int k = 0;
        dfs(tree, 0, -1, 0, k);
        for (int i = 0; i < V; ++i) {
          if (isG[i] == 1) seg.init_set(vf[i], pint(1, 0));
          else seg.init_set(vf[i], pint(0, 1));
        }
        seg.init_tree();
    }
    
    void dfs(const Graph &tree, int v, int par, int dep, int &ord) {
        node[ord] = v;
        depth[ord] = dep;
        vf[v] = ve[v] = ord;
        ++ord;
        for (int i = 0; i < tree[v].size(); ++i) {
            auto e = tree[v][i];
            if (e != par) {
                dfs(tree, e, v, dep+1, ord);
                node[ord] = v;
                depth[ord] = dep;
                ve[v] = ord;
                ++ord;
            }
        }
    }

    void update(int v) {
        seg.set(vf[v], ve[v] + 1, 1);
    }

    pint get() {
        return seg.get(0, seg.size_seg);
    }
    
    //void print() { COUT(node); COUT(vf); COUT(ve); seg.print(); }
};

int main() {
    cin >> N >> Q;
    tree.clear(); tree.resize(N);
    isG.resize(N);
    for (int i = 0; i < N-1; ++i) {
        int p; cin >> p; --p;
        tree[i+1].push_back(p);
        tree[p].push_back(i+1);
    }
    for (int i = 0; i < N; ++i) {
        char c; cin >> c;
        if (c == 'G') isG[i] = 1;
        else isG[i] = 0;
    }
    EulerTour et(tree);
    for (int q = 0; q < Q; ++q) {
        int v; cin >> v; --v;
        et.update(v);
        pint p = et.get();
        if (p.first > p.second) cout << "broccoli" << endl;
        else cout << "cauliflower" << endl;
    }
}