Submission #1033208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033208		juicy	XORanges (eJOI19_xoranges)	C++17	100 / 100	68 ms	8024 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

struct Fenwick {
	int s[N];

	void upd(int i, int x) {
		for (; i < N; i += i & -i) {
			s[i] ^= x;
		}
	}

	int qry(int i) {
		int res = 0;
		for (; i; i -= i & -i) {
			res ^= s[i];
		}
		return res;
	}

	int qry(int l, int r) {
		return qry(r) ^ qry(l - 1);
	}
} ft[2];

int n, q;
int a[N];

int qry(int l, int r) {
	if (l % 2 != r % 2) {
		return 0;
	}
	return ft[l & 1].qry((l + 1) / 2, (r + 1) / 2);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		ft[i & 1].upd((i + 1) / 2, a[i]);
	}
	while (q--) {
		int type; cin >> type;
		if (type == 1) {
			int i, j; cin >> i >> j;
			ft[i & 1].upd((i + 1) / 2, j ^ a[i]);
			a[i] = j;
		} else {
			int l, r; cin >> l >> r;
			cout << qry(l, r) << "\n";
		}
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25