mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum

問題

codeforces.com

数列 A に対して, 以下のクエリに答えよ。

  • 区間 [l, r] に偶数個ある整数の xor を取る
解法

偶数じゃなくて奇数だったら簡単です。というのも, xor は 2 回同じ数をかけられれば自動的に 0 になるので [l, r] の区間の xor を累積和で適当にやれば良いだけだからです。

ですが, これは偶数の場合を聞いているので, 答えるべきものとしては [l, r] の累積xor から, [l, r] に存在する数の xor の和を取ったもの, になります。

累積和は簡単なので, 区間 [l, r] におけるユニークな数の xor 和を考えます。

クエリを R の順番に並べます。で, ある数がすでに表れていた場合には前回現れたところはすべて無効化するような感じにします。具体的には

last[num] = (num が最後に出てくる index) というようにすると, i 番目に num が出てきた場合, A[last[num]] ^= num とやることによって解決します。こういう風にすれば bit なりセグメント木なりで区間 xor の問題に落とせます。

// 0-based Binary Indexed Tree
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s ^= bit[i]);
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] ^= x);
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)^sum(a);
    }
};

const int MAXN = 1001000;
int A[MAXN], S[MAXN], L[MAXN], R[MAXN];
int ans[MAXN];
vector<int> G[MAXN];

int main() {
    int N, M;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", A+i);
    for (int i = 1; i <= N; i++)
        S[i] = S[i-1]^A[i-1];
    cin >> M;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", L+i, R+i);
        L[i]--;
        ans[i] = S[R[i]]^S[L[i]];
        G[R[i]].push_back(i);
    }
    BIT<int> bit(MAXN);
    map<int, int> last;
    for (int i = 0; i < N; i++) {
        bit.add(i, A[i]);
        if (last.find(A[i]) != last.end()) {
            bit.add(last[A[i]], A[i]);
        }
        for (int j : G[i+1]) {
            ans[j] ^= bit.sum(L[j], i+1);
        }
        last[A[i]] = i;
    }
    for (int i = 0; i < M; i++)
        printf("%d\n", ans[i]);
    return 0;
}