ABC（AtCoder Beginner Contest）185 のF問題をC++で解いてみました。セグメント木の演習です。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Range Xor Query（Difficulty : 1053）
問題はリンク先をご覧ください。
セグメント木を使う典型問題です。AtCoder Problems による Difficulty は 1053 でした。
解答案
ABC185は、2020年12月13日に開催されています。このときのコンテストは、F問題までの6題しか出題されていませんでした。最後の問題でしたが、セグメント木が分かっていれば解きやすい問題でした。
セグメント木については、この記事で紹介しています。
セグメント木を使うには、二項演算 op と単位元 e を定義する必要があります。この問題では、op は、xor の結果を返す関数となります。e は 0 となります。
C++ プログラム例（ABC185F）
まず、自前ライブラリで解いてみます。関数 op と単位元 e を与えて、セグメント木を定義します（69行目）。後は、クエリに従い、1点更新（80行目）と範囲の演算結果を返す（83行目）だけです。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
private:
vector<int> data;
int (*op)(int, int);
int e;
public:
int size;
SegmentTree(int n, int (*_op)(int, int), int _e) {
op = _op;
e = _e;
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size - 1, e);
}
int get(int k) {
return data[k + size - 1];
}
void update(int k, int a) {
k += size - 1;
data[k] = a;
while (k > 0) {
k = (k - 1) / 2;
data[k] = op(data[k * 2 + 1], data[k * 2 + 2]);
}
}
int query(int a, int b) {
return query_sub(a, b, 0, 0, size);
}
// call ST.query(a, b, 0, 0, size);
int query_sub(int a, int b, int k, int l, int r) {
if ((r <= a)||(b <= l)) {
return e;
}
if ((a <= l)&&(r <= b)) {
return data[k];
} else {
int vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return op(vl, vr);
}
}
};
int op(int a, int b)
{
return a ^ b;
}
int main()
{
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
SegmentTree st(n + 1, op, 0);
for (int i = 0; i < n; ++i) {
st.update(i, a[i]);
}
for (int i = 0; i < q; ++i) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) {
--x;
a[x] ^= y;
st.update(x, a[x]);
} else if (type == 2) {
--x;
cout << st.query(x, y) << endl;
}
}
return 0;
}ACL で、セグメント木クラス segtree も提供されています。以下は、segtree を使ったプログラムです。
#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
int op(int a, int b)
{
return a ^ b;
}
int e(void)
{
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> st(n + 1);
for (int i = 0; i < n; ++i) {
st.set(i, a[i]);
}
for (int i = 0; i < q; ++i) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) {
--x;
a[x] ^= y;
st.set(x, a[x]);
} else if (type == 2) {
--x;
cout << st.prod(x, y) << endl;
}
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
最後に
セグメント木の演習を増やすために記事を書きました。セグメント木についての記事は、タグから検索できます。
引き続き ABC の問題を紹介していきます。
