Submission #638496

#	Time	Username	Problem	Language	Result	Execution time	Memory
638496		gagik_2007	XORanges (eJOI19_xoranges)	C++17	100 / 100	519 ms	16084 KiB

xoranges

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef double ld;
typedef int itn;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll SAFEINF = 1e12;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 2e5 + 7;
ll n, m, k;
ll tz[800007];
ll tk[800007];
ll a[200007];

void buildz(int v, int tl, int tr) {
	if (tl == tr) {
		if (tl % 2 == 0) {
			tz[v] = a[tl];
		}
		else tz[v] = 0;
	}
	else {
		int tm = (tl + tr) / 2;
		buildz(2 * v, tl, tm);
		buildz(2 * v + 1, tm + 1, tr);
		tz[v] = tz[2 * v] ^ tz[2 * v + 1];
	}
}

void buildk(int v, int tl, int tr) {
	if (tl == tr) {
		if (tl % 2 == 1) {
			tk[v] = a[tl];
		}
		else tk[v] = 0;
	}
	else {
		int tm = (tl + tr) / 2;
		buildk(2 * v, tl, tm);
		buildk(2 * v + 1, tm + 1, tr);
		tk[v] = tk[2 * v] ^ tk[2 * v + 1];
	}
}

void updatez(int v, int tl, int tr, int ind, ll val) {
	if (tl == tr) {
		tz[v] = val;
	}
	else {
		int tm = (tl + tr) / 2;
		if (ind <= tm) {
			updatez(2 * v, tl, tm, ind, val);
		}
		else updatez(2 * v + 1, tm + 1, tr, ind, val);
		tz[v] = tz[2 * v] ^ tz[2 * v + 1];
	}
}

void updatek(int v, int tl, int tr, int ind, ll val) {
	if (tl == tr) {
		tk[v] = val;
	}
	else {
		int tm = (tl + tr) / 2;
		if (ind <= tm) {
			updatek(2 * v, tl, tm, ind, val);
		}
		else updatek(2 * v + 1, tm + 1, tr, ind, val);
		tk[v] = tk[2 * v] ^ tk[2 * v + 1];
	}
}

ll sumz(int v, int tl, int tr, int l, int r) {
	if (l > r)return 0;
	if (tl >= l && tr <= r)return tz[v];
	else {
		int tm = (tl + tr) / 2;
		return sumz(2 * v, tl, tm, l, min(tm, r)) ^
			sumz(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
	}
}

ll sumk(int v, int tl, int tr, int l, int r) {
	if (l > r)return 0;
	if (tl >= l && tr <= r)return tk[v];
	else {
		int tm = (tl + tr) / 2;
		return sumk(2 * v, tl, tm, l, min(tm, r)) ^
			sumk(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
	}
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	buildk(1, 0, n - 1);
	buildz(1, 0, n - 1);
	for (int i = 0; i < k; i++) {
		int tp;
		ll x, y;
		cin >> tp >> x >> y;
		if (tp == 1) {
			x--;
			if (x % 2 == 0) {
				updatez(1, 0, n - 1, x, y);
			}
			else updatek(1, 0, n - 1, x, y);
		}
		else {
			x--, y--;
			if ((y - x + 1) % 2 == 0) {
				cout << 0 << endl;
			}
			else {
				if (x % 2 == 0) {
					cout << sumz(1, 0, n - 1, x, y) << endl;
				}
				else cout << sumk(1, 0, n - 1, x, y) << endl;
			}
		}
	}
	return 0;
}

/*
4 20
2
3
2
2

*/

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