square869120Contest #2 H - Counting 1's (その 2)

平方分割でも解けたので紹介しようかなと。

問題

s8pc-2.contest.atcoder.jp

解法

bit[i] = (i 番目の bit がどうなっているか) flag[i] = ([i*B, (i+1)*B) 番目の bit は bit[i] から反転させたものになっているか, cnt[i] = ([i*B, (i+1)*B) で立っている bit の数) とします。

すると, flag[i] = 0 の時は cnt[i] の値がそのまま対応する区間に立っている bit の数で, flag[i] = 1 のときは B-cnt[i] が対応する区間に立っている bit の数になります。

適当に flag, cnt, bit を管理してクエリに答えていけば良いです。

const int B = 300;
const int MAXN = 100010;
int bit[MAXN], flag[MAXN/B+10], cnt[MAXN/B+10], sz[MAXN/B+10];
int to[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        to[i] = i/B;
        sz[to[i]]++;
    }
    while (Q--) {
        int q, l, r;
        cin >> q >> l >> r;
        if (q == 1) {
            int tl = l, tr = r;
            while (tl < tr && tl%B != 0) {
                bit[tl] ^= 1;
                if (bit[tl]) cnt[to[tl]]++;
                else cnt[to[tl]]--;
                tl++;
            }
            while (tl < tr && tr%B != 0) {
                tr--;
                bit[tr] ^= 1;
                if (bit[tr]) cnt[to[tr]]++;
                else cnt[to[tr]]--;
            }
            while (tl < tr) {
                flag[to[tl]] ^= 1;
                tl += B;
            }
        } else {
            int tl = l, tr = r, ans = 0;
            while (tl < tr && tl % B != 0) {
                if (flag[to[tl]] != bit[tl]) ans++;
                tl++;
            }
            while (tl < tr && tr % B != 0) {
                tr--;
                if (flag[to[tr]] != bit[tr]) ans++;
            }
            while (tl < tr) {
                int i = to[tl];
                if (!flag[i]) ans += cnt[i];
                else ans += sz[i]-cnt[i];
                tl += B;
            }
            cout << ans << endl;
        }
    }
    return 0;
}