Submission #466146

#	Time	Username	Problem	Language	Result	Execution time	Memory
466146		Stickfish	XORanges (eJOI19_xoranges)	C++17	100 / 100	633 ms	7112 KiB

xoranges

#include <iostream>
#include <vector>
using namespace std;

struct stree{
	void resize(int n){
		sz = 1;
		while(sz < n)sz <<= 1;
		t.assign(sz * 2 - 1, 0);
	}

	void xori(int i, int x){
		i += sz - 1;
		while(true){
			t[i] ^= x;
			i = (i - 1) / 2;
			if(i == 0)
				return;
		}
	}

	int get(int l, int r){
		l += sz - 1;
		r += sz - 2;
		int ans = 0;
		while(l <= r){
			if(l % 2 == 0)
				ans ^= t[l];
			l = l / 2;
			if(r % 2)
				ans ^= t[r];
			r = r / 2 - 1;
		}
		return ans;
	}
private:
	int sz;
	vector<int> t;
};

const int MAXN = 2e5 + 123;
int a[MAXN];

signed main(){
	int n, q;
	cin >> n >> q;
	stree sodd;
	stree seven;
	sodd.resize(n);
	seven.resize(n);
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		if(i % 2){
			sodd.xori(i, a[i]);
		} else {
			seven.xori(i, a[i]);
		}
	}
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int i, x;
			cin >> i >> x;
			--i;
			if(i % 2)
				sodd.xori(i, a[i] ^ x);
			else
				seven.xori(i, a[i] ^ x);
			a[i] = x;
		} else {
			int l, r;
			cin >> l >> r;
			--l;
			if((r - l) % 2 == 0){
				cout << 0 << '\n';
				continue;
			}
			int ans = 0;
			if(l % 2)
				ans = sodd.get(l, r);
			else
				ans = seven.get(l, r);
			cout << ans << '\n';
		}
	}
}

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