けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 185 F - Range Xor Query (緑色, 600 点)

ABC-F が緑色 diff になったのは史上初かな!?!???
でもセグ木が緑色はびっくり!!!

問題概要

長さ  N の非負整数列  A_{1}, \dots, A_{N} がある。これに対して以下の  Q 個のクエリに答えよ。

  • タイプ 1:整数  x, y が与えられる。 A_{x} A_{x} XOR  y で置き換えよ。
  • タイプ 2:整数  x, y が与えられる。 A_{x} XOR  A_{x+1} XOR ... XOR  A_{y} の値を出力せよ。

制約

  •  1 \le N, Q \le 3 \times 10^{5}

解法 (1):セグメント木を使う

今回のように、

  • 配列の 1 点のみを更新する
  • 配列の区間についての総和 (今回は XOR 和についての総和) を求める

という処理を高速に実現できるデータ構造として、セグメント木がある。

ACL にはセグメント木があるので、それを使うだけで AC がとれる!!!

1 回のクエリにかかる計算量は  O(\log N) なので、全体の計算量は  O(N + Q\log N) となる。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

// セグメント木の二項演算 (XOR 和)
int op(int a, int b) {
    return a ^ b;
}

// 単位元 (今回は 0)
int e() {
    return 0;
}

int main() {
    int N, Q; cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    segtree<int, op, e> seg(A);
    for (int q = 0; q < Q; ++q) {
        int t, x, y;
        cin >> t >> x >> y;
        --x;
        if (t == 1) {
            // 元の値
            int v = seg.get(x);

            // 変更後の値
            v ^= y;

            // 更新
            seg.set(x, v);
        }
        else {
            cout << seg.prod(x, y) << endl;
        }
    }
}

解法 (2):BIT

もう 1 つ BIT を使う手もある。BIT とは

  • (加算) 整数  x, v が与えられ、 A_{x} +=  v を行う
  • (総和) 区間  \lbrack l, r) が与えられ、その区間の総和を求める

という処理をそれぞれ  O(\log N) でこなすデータ構造だ。そして BIT の

  • 「+」 (通常の加算) という演算を
  • 「^」 (XOR) という演算へと書き換える

だけで、通すことができる!!! 計算量は同じく  O(N + Q \log N) となる。

具体的に書き換えるのは 3 箇所。なお、BIT では「逆演算」ができることが必要となる。足し算「+」の逆演算は引き算「-」である。XOR 和演算「^」の逆演算は、実は「^」そのものである!!

もう少し具体的に考えてみる。

a ^ b = c (足し算)

であるとき、

c ? b = a (引き算)

となるような、逆演算「?」を定義したいのだ。しかし実は、a ^ b = c の両辺に ^b をとると

c ^ b = a

となる。これは、「^」そのものが「^」の逆演算でもあることを意味している。

#include <bits/stdc++.h>
using namespace std;

template <class Abel> struct BIT {
    Abel UNITY_SUM = 0;
    vector<Abel> dat;
    
    // [0, n)
    BIT(int n, Abel unity = 0) : UNITY_SUM(unity), dat(n, unity) { }
    void init(int n) {
        dat.assign(n, UNITY_SUM);
    }
    
    // a is 0-indexed
    inline void add(int a, Abel x) {
        for (int i = a; i < (int)dat.size(); i |= i + 1)
            dat[i] = dat[i] ^ x;
    }
    
    // [0, a), a is 0-indexed
    inline Abel sum(int a) {
        Abel res = UNITY_SUM;
        for (int i = a - 1; i >= 0; i = (i & (i + 1)) - 1)
            res = res ^ dat[i];
        return res;
    }
    
    // [a, b), a and b are 0-indexed
    inline Abel sum(int a, int b) {
        return sum(b) ^ sum(a);
    }
    
    // debug
    void print() {
        for (int i = 0; i < (int)dat.size(); ++i)
            cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    BIT<long long> bit(N+1);
    for (int i = 0; i < N; ++i) bit.add(i, A[i]);

    for (int _ = 0; _ < Q; ++_) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            --x;
            bit.add(x, y);
        }
        else {
            --x;
            cout << bit.sum(x, y) << endl;
        }
    }
}