AtCoder

ABC185 F問題(Range Xor Query)を解く

AtCoder_ABC185_F

ABC(AtCoder Beginner Contest)185 のF問題をC++で解いてみました。セグメント木の演習です。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

F問題 Range Xor Query(Difficulty : 1053)

問題はリンク先をご覧ください。

ABC185 F問題 Range Xor Query

セグメント木を使う典型問題です。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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA