Codeforces #149 XOR on Segment

問題概要

n個の正数a₁, a₂, ..., a_nからなる配列aに対して、以下の2種類のクエリーが複数回投げられるので高速に処理せよ。

1. (l, r)が与えられるので、[a_l, a_r]の和を求める。
2. (l, r, x)が与えられるので、a_i := a_i xor x, i = l, l+1, ..., rのようにaの値を更新する。

タイプ1.のクエリについてのみ結果を出力せよ。

方針

とりあえず、雰囲気的にセグメント木を使うのは分かる。あとビット毎に独立して処理すればいいのも分かった（TopCoderで似たような問題といたため）。更新系の処理をうまく書く方法がすぐには浮かばなかったけど、

• 小さなセグメントにupdateをかけて、それを含む大きなセグメントにreadが投げられたらどうするか？
• 大きなセグメントにupdateをかけて、それに含まれる小さなセグメントにreadが投げられたらどうなるか？

を考えて、うまく行くようにいろいろ書いていたら、出来てた。

セグメント木、得意ではないですが好きです。

ソースコード

#include <iostream>

using namespace std;

int n, m;
int segsum[30][1<<18];
int segflip[30][1<<18];

void update(int pos, int k, int l, int r, int a, int b) {
    if (r <= a || b <= l)
        return;
    if (a <= l && r <= b) {
        segflip[pos][k] ^= 1;
        segsum[pos][k] = r-l-segsum[pos][k];
    } 
    else {
        int c = (l+r) >> 1;
        update(pos, 2*k+1, l, c, a, b);
        update(pos, 2*k+2, c, r, a, b);
        segsum[pos][k] = segsum[pos][2*k+1] + segsum[pos][2*k+2];
        if (segflip[pos][k])
            segsum[pos][k] = r-l-segsum[pos][k];
    }
}

int read(int pos, int k, int l, int r, int a, int b) {
    if (r <= a || b <= l)
        return 0;
    if (a <= l && r <= b)
        return segsum[pos][k];
    int c = (l+r) >> 1;
    int ret = 0;
    ret += read(pos, 2*k+1, l, c, a, b);
    ret += read(pos, 2*k+2, c, r, a, b);
    if (segflip[pos][k])
        ret = min(r, b) - max(l, a) - ret;
    return ret;
}

void insert(int pos, int k, int l, int r, int x) {
    if (x < l || r <= x)
        return;
    if (r - l == 1)
        segsum[pos][k]++;
    else {
        int c = (l+r) >> 1;
        insert(pos, 2*k+1, l, c, x);
        insert(pos, 2*k+2, c, r, x);
        segsum[pos][k] = segsum[pos][2*k+1] + segsum[pos][2*k+2];
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        for (int j = 0; j < 30; j++) {
            if (a & 1 << j)
                insert(j, 0, 0, n, i);
        }
    }
    
    cin >> m;
    while (m--) {
        int type, l, r, x;
        cin >> type;
        if (type == 1) {
            cin >> l >> r;
            long long ret = 0;
            for (int k = 0; k < 30; k++)
                ret += (long long)read(k, 0, 0, n, l-1, r) << k;
            cout << ret << endl;
        }
        else {
            cin >> l >> r >> x;
            for (int k = 0; k < 30; k++)
                if (x & 1 << k)
                    update(k, 0, 0, n, l-1, r);
        }
    }

    return 0;
}