【AtCoder】ABC 185 F - Range Xor Query

2026-11-07

AtCoder/ABC/F問題 AtCoder/ABC/600点問題 AtCoder/緑Diff AtCoder/NoviSteps/1Q AtCoder/データ構造/Segment Tree AtCoder/数学/XOR 競技プログラミング

F - Range Xor Query

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 3 sec / メモリ制限: 1024 MiB / Difficulty: 1053 / NoviSteps: 1Q / 配点: 600 点

問題概要

長さ $N$ の整数列 $A$ があり、今からこの数列について $Q$ 個のクエリを処理する。 $i$ 番目のクエリでは $T_i, X_i, Y_i$ が与えられるので、以下の処理をせよ。

$T_i = 1$ のとき: $A_{X_i}$ を $A_{X_i} \oplus Y_i$ で置き換える
$T_i = 2$ のとき: $A_{X_i} \oplus A_{X_i + 1} \oplus A_{X_i + 2} \oplus \dots \oplus A_{Y_i}$ を出力する

制約

$1 \le N \le 300000$
$1 \le Q \le 300000$
$0 \le A_i \lt 2^{30}$
$T_i$ は $1$ または $2$
$T_i = 1$ なら $1 \le X_i \le N$ かつ $0 \le Y_i \lt 2^{30}$
$T_i = 2$ なら $1 \le X_i \le Y_i \le N$
入力は全て整数

考察

クエリ内容は XOR 演算による数列の1点更新と区間 XOR の取得である。

XOR は単位元 $0$ を持ち結合法則を満たすので、数列全体を Segment Tree で管理すれば、各クエリを $O(\log N)$ で処理できる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
10. 
11.using ll = long long;
12. 
13.// ======================================== //
14. 
15.ll op(ll a, ll b) { return a ^ b; }
16.ll e() { return 0LL; }
17. 
18.int main()
19.{
20.    int N, Q;
21.    cin >> N >> Q;
22.    segtree<ll, op, e> A(N);
23.    rep(i, 0, N) {
24.        ll a;
25.        cin >> a;
26.        A.set(i, a);
27.    }
28. 
29.    while (Q--)
30.    {
31.        int T;
32.        ll X, Y;
33.        cin >> T >> X >> Y;
34. 
35.        if (T == 1)
36.        {
37.            A.set(X - 1, A.get(X - 1) ^ Y);
38.        }
39.        else if (T == 2)
40.        {
41.            cout << A.prod(X - 1, Y) << endl;
42.        }
43.    }
44. 
45.    return 0;
46.}