square869120Contest #2 H - Counting 1's

問題

s8pc-2.contest.atcoder.jp

解法

遅延評価セグメント木で解きました。

update で [l, r) の区間を反転させ, query で [l, r) の 1 の数を求めるような機能を実現します。

lazy 配列には「今考えている区間は後で反転させるつもりか」というのを覚えておきます。後はコード見ましょう。

// 遅延評価つきセグメント木
// update: [l, r) の区間を反転させる
// query:  [l, r) の 1 の数の和を求める
// lazy を反転フラグにすればﾕｰﾃｲｹﾙｯｼｮ
struct ST {
    vector<int> seg, lazy;
    int size;

    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(size * 2);
        lazy.resize(size * 2);
    }

    inline void push(int k, int l, int r) {
        if (lazy[k] != 0) {
            seg[k] = (r-l)-seg[k];
            if (r - l > 1) {
                lazy[k * 2 + 1] ^= lazy[k];
                lazy[k * 2 + 2] ^= lazy[k];
            }
            lazy[k] = 0;
        }
    }

    inline int merge(int x, int y) {
        return x + y;
    }

    void update(int a, int b, int k, int l, int r) {
        push(k, l, r);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            lazy[k] = 1;
            push(k, l, r);
        } else {
            update(a, b, k * 2 + 1, l, (l + r) / 2);
            update(a, b, k * 2 + 2, (l + r) / 2, r);
            seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]);
        }
    }

    void update(int a, int b) {
        return update(a, b, 0, 0, size);
    }

    int query(int a, int b, int k, int l, int r) {
        push(k, l, r);
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        int x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return merge(x, y);
    }

    ll query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, Q;
    cin >> n >> Q;
    ST seg(n);
    while (Q--) {
        int q, l, r;
        cin >> q >> l >> r;
        if (q==1) {
            seg.update(l, r);
        } else {
            cout << seg.query(l, r) << endl;
        }
    }
    return 0;
}