Submission #649471

#	Time	Username	Problem	Language	Result	Execution time	Memory
649471		ymm	XORanges (eJOI19_xoranges)	C++17	100 / 100	96 ms	7628 KiB

xoranges

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
int arr[2][N];
int fen[2][N];
int n, q;

void up(int i, int x, int *fen)
{
	++i;
	while (i < N) {
		fen[i] ^= x;
		i += i & -i;
	}
}
int get(int r, int *fen)
{
	int ans = 0;
	while (r > 0) {
		ans ^= fen[r];
		r ^= r & -r;
	}
	return ans;
}
int get(int l, int r, int *fen)
{
	return get(r, fen) ^ get(l, fen);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> q;
	Loop (i,0,n) {
		cin >> arr[i&1][i/2];
		up(i/2, arr[i&1][i/2], fen[i&1]);
	}
	while (q--) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t == 1) {
			--x;
			up(x/2, arr[x&1][x/2] ^ y, fen[x&1]);
			arr[x&1][x/2] = y;
		}
		if (t == 2) {
			--x; --y;
			if (x%2 != y%2)
				cout << "0\n";
			else
				cout << get(x/2, y/2+1, fen[x&1]) << '\n';
		}
	}
}

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