Submission #467217

#	Time	Username	Problem	Language	Result	Execution time	Memory
467217		syrtin	XORanges (eJOI19_xoranges)	C++17	100 / 100	217 ms	11000 KiB

xoranges

/*author:	syrtin*/
#include <bits/stdc++.h>

#define pb push_back
#define all(v) v.begin(),v.end()
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair < int, int > pii;
typedef vector<int> vi;
typedef vector<long long> vll;

const int N = 2e5 + 1;
const ll MOD = 1e9 + 7;
const int inf = int(1e9);
const ll INF = ll(1e16);

ll x, l, r, tr[N * 4], od[N * 4], a[N], j;
void build(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		tr[v] = a[xl];
		return;
	}
	build(v * 2 + 1, xl, xl + (xr - xl) / 2), build(v * 2 + 2, xl + (xr - xl) / 2, xr);
	tr[v] = tr[v * 2 + 1] ^ tr[v * 2 + 2];
}
void bld(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		od[v] = a[xl * 2];
		return;
	}
	bld(v * 2 + 1, xl, xl + (xr - xl) / 2), bld(v * 2 + 2, xl + (xr - xl) / 2, xr);
	od[v] = od[v * 2 + 1] ^ od[v * 2 + 2];
}
void up(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		od[v] = x;
		return;
	}
	if(xl + (xr - xl) / 2 <= j)up(v * 2 + 2, xl + (xr - xl) / 2, xr);
	else up(v * 2 + 1, xl, xl + (xr - xl) / 2);
	od[v] = od[v * 2 + 1] ^ od[v * 2 + 2];
}
void upd(int v, int xl, int xr) {
	if(xl + 1 == xr) {
		tr[v] = x;
		return;
	}
	if(xl + (xr - xl) / 2 <= j)upd(v * 2 + 2, xl + (xr - xl) / 2, xr);
	else upd(v * 2 + 1, xl, xl + (xr - xl) / 2);
	tr[v] = tr[v * 2 + 1] ^ tr[v * 2 + 2];
}
int get(int v, int xl, int xr) {
	if(xl >= l && r >= xr)return tr[v];
	if(xl >= r || l >= xr)return 0;
	return get(v * 2 + 1, xl, xl + (xr - xl) / 2) ^ get(v * 2 + 2, xl + (xr - xl) / 2, xr);
}
int gg(int v, int xl, int xr) {
	if(xl >= l && r >= xr)return od[v];
	if(xl >= r || l >= xr)return 0;
	return gg(v * 2 + 1, xl, xl + (xr - xl) / 2) ^ gg(v * 2 + 2, xl + (xr - xl) / 2, xr);
}
void SOLVE(/*WATLE*/) {
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	build(0, 0, n);
	bld(0, 0, (n + 1) / 2);
	while(q--) {
		int wt;
		cin >> wt;
		if(wt == 1) {
			cin >> j >> x;
			j--;
			upd(0, 0, n);
			if(j % 2 == 0)j /= 2, up(0, 0, (n + 1) / 2);
		}
		else {
			cin >> l >> r;
			l--;
			if((r - l) % 2 == 0)cout << 0 << '\n';
			else {
				if(l % 2){
					int s = get(0, 0, n);
					l = l / 2 + 1, r /= 2;
					cout << int(s ^ int(gg(0, 0, (n + 1) / 2))) << '\n';
				}
				else {
					l = l / 2, r = r / 2 + 1;
					cout << gg(0, 0, (n + 1) / 2) << '\n';					
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int times = 1;
	//cin >> times;
    for(int i = 1; i <= times; i++) {
        //cout << "Case #" << t << ": ";
        SOLVE();
    }
    return 0;
}

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