Submission #585165

#	Time	Username	Problem	Language	Result	Execution time	Memory
585165		algorithm16	XORanges (eJOI19_xoranges)	C++14	100 / 100	548 ms	8676 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 7;

int n, q;
int a[maxn], fenp[maxn], fennp[maxn];

void add (int x, int val) {
	if (x & 1) {
		for (; x < maxn; x += x & -x) {
			fennp[x] ^= val;
		}
	}
	else {
		for (; x < maxn; x += x & -x) {
			fenp[x] ^= val;
		}
	}
}

int query (int x) {
	int out = 0;
	if (x & 1) {
		for (; x > 0; x -= x & -x) {
			out ^= fennp[x];
		}
	}
	else {
		for (; x > 0; x -= x & -x) {
			out ^= fenp[x];
		}
	}
	return out;
}

int main () {
	cin >> n >> q;
	
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		add(i+1, a[i]);
	}
	
	for (int i = 0; i < q; i++) {
		int ot; cin >> ot; --ot;
		if (ot) {
			int a, b;
			cin >> a >> b;
			if ((b - a) & 1) cout << "0\n";
			else {
				b -= (b - a) & 1;
				cout << (query(b) ^ query(a - 2)) << "\n";
			}
			
		}
		else {
			int x, val;
			cin >> x >> val;
			add(x, a[x-1]);
			add(x, val);
			a[x-1] = val;
		}
	}
	
	return 0;
}

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