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;
        }
    }
}

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

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

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

問題概要

制約

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

コード

解法 (2)：BIT