Codeforces Round #499 (Div. 1): D. Mars rover

note

• MLEが厳しいという話が聞こえた
• 類問: codeFlyer （bitFlyer Programming Contest）オープンコンテスト: E - 数式とクエリ
• 要素が葉に対応するsegment木を持ちながら構文木を畳むやつは典型扱いで覚えていたが、よく考えると常にDFSで置き換えられる

solution

Euler tourして区間操作/点取得のsegment木で管理して$O(n \log n)$。 あるいは2回DFSで$O(n)$。どちらもやってることは同じ。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef typename OperatorMonoid::underlying_type operator_type;
    typedef typename OperatorMonoid::target_type underlying_type;
    int n;
    vector<operator_type> f;
    vector<underlying_type> a;
    const OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n-1, op.unit());
    }
    underlying_type point_get(int i) { // 0-based
        underlying_type acc = a[i];
        for (i = (i+n)/2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i-1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i-n+1] = op.apply(z, a[i-n+1]);
            }
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2*i+1, il, (il+ir)/2, 0, n, f[i]);
            range_apply(2*i+2, (il+ir)/2, ir, 0, n, f[i]);
            f[i] = op.unit();
            range_apply(2*i+1, il, (il+ir)/2, l, r, z);
            range_apply(2*i+2, (il+ir)/2, ir, l, r, z);
        }
    }
};

enum op_t {
    OP_NOP = -1,
    OP_ZERO = 0,
    OP_ONE = 1,
    OP_FLIP = 2,
};
struct operator_monoid {
    typedef op_t underlying_type;
    typedef bool target_type;
    op_t unit() const {
        return OP_NOP;
    }
    op_t append(op_t a, op_t b) const {
        if (a == OP_NOP) {
            return b;
        } else if (a == OP_ZERO or a == OP_ONE) {
            return a;
        } else if (a == OP_FLIP) {
            if (b == OP_NOP) {
                return OP_FLIP;
            } else if (b == OP_ZERO) {
                return OP_ONE;
            } else if (b == OP_ONE) {
                return OP_ZERO;
            } else if (b == OP_FLIP) {
                return OP_NOP;
            }
        }
        assert (false);
    }
    bool apply(op_t a, bool b) const {
        if (a == OP_NOP) {
            return b;
        } else if (a == OP_ZERO) {
            return false;
        } else if (a == OP_ONE) {
            return true;
        } else if (a == OP_FLIP) {
            return not b;
        }
        assert (false);
    }
};

constexpr int IN = 1;
constexpr int AND = 2;
constexpr int OR = 3;
constexpr int XOR = 4;
constexpr int NOT = 5;
constexpr int root = 0;

int main() {
    // input
    int n; scanf("%d", &n);
    vector<array<int, 3> > g(n);
    int k = 0;
    REP (i, n) {
        char buf[16]; scanf("%s", buf);
        string s(buf);
        if (s == "IN") {
            scanf("%d", &g[i][1]);
            g[i][0] = IN;
            ++ k;
        } else if (s == "NOT") {
            scanf("%d", &g[i][1]);
            -- g[i][1];
            g[i][0] = NOT;
        } else {
            scanf("%d%d", &g[i][1], &g[i][2]);
            -- g[i][1];
            -- g[i][2];
            if (s == "AND") {
                g[i][0] = AND;
            } else if (s == "OR") {
                g[i][0] = OR;
            } else if (s == "XOR") {
                g[i][0] = XOR;
            } else {
                assert (false);
            }
        }
    }

    // solve
    vector<int> left(n);
    vector<int> right(n); {
        function<int (int, int)> go = [&](int i, int l) {
            left[i] = l;
            if (g[i][0] == IN) {
                right[i] = l + 1;
                return 1;
            } else if (g[i][0] == NOT) {
                int k = go(g[i][1], l);
                right[i] = l + k;
                return k;
            } else {
                int k = go(g[i][1], l);
                k += go(g[i][2], l + k);
                right[i] = l + k;
                return k;
            }
        };
        go(root, 0);
    }
    dual_segment_tree<operator_monoid> segtree(k, 0);
    function<bool (int)> go = [&](int i) {
        if (g[i][0] == IN) {
            segtree.range_apply(left[i], right[i], g[i][1] ? OP_ZERO : OP_ONE);
            return (bool)g[i][1];
        } else if (g[i][0] == NOT) {
            bool x = go(g[i][1]);
            segtree.range_apply(left[i], right[i], OP_FLIP);
            return not x;
        } else {
            int middle = right[g[i][1]];
            bool x = go(g[i][1]);
            bool y = go(g[i][2]);
            if (g[i][0] == AND) {
                if (not y) segtree.range_apply(left[i], middle, OP_ZERO);
                if (not x) segtree.range_apply(middle, right[i], OP_ZERO);
                return x and y;
            } else if (g[i][0] == OR) {
                if (y) segtree.range_apply(left[i], middle, OP_ONE);
                if (x) segtree.range_apply(middle, right[i], OP_ONE);
                return x or y;
            } else if (g[i][0] == XOR) {
                if (y) segtree.range_apply(left[i], middle, OP_FLIP);
                if (x) segtree.range_apply(middle, right[i], OP_FLIP);
                return x != y;
            }
            assert (false);
        }
    };
    go(root);

    // output
    REP (i, n) if (g[i][0] == IN) {
        printf("%d", segtree.point_get(left[i]));
    }
    printf("\n");
    return 0;
}