Submission #1125801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125801		heey	XORanges (eJOI19_xoranges)	C++20	100 / 100	105 ms	8076 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
int n;
int seg[4*maxn], sego[4*maxn];
int a[maxn], b[maxn];
void build(int v, int l, int r){
	if(l == r) {
		seg[v] = a[l];
		return;
	}

	int m = (l+r)>>1;
	build(v<<1, l, m);
	build(v<<1|1, m+1, r);
	seg[v] = seg[v<<1] ^ seg[v<<1|1];
}

void update(int pos, int val, int nod, int tl, int tr){
	if(tl == tr) {
		seg[nod] = val;
		a[pos] = val;
		return;
	}

	int m = (tl+tr)>>1;
	if(pos <= m) update(pos, val, nod<<1, tl, m);
	else update(pos, val, nod<<1|1, m+1, tr);

	seg[nod] = seg[nod<<1] ^ seg[nod<<1|1];
}

int query(int l, int r, int nod, int tl, int tr){
	if(tl > r || tr < l || tl > tr) return 0;
	if(tl >= l && tr <= r) return seg[nod];

	int mid = (tl+tr)>>1;
	return query(l, r, nod<<1, tl, mid) ^ query(l, r, nod<<1|1, mid+1, tr);
}

void build2(int v, int l, int r){
	if(l == r){
		sego[v] = b[l];
		return;
	}

	int m = (l+r)>>1;
	build2(v<<1, l, m);
	build2(v<<1|1, m+1, r);
	sego[v] = sego[v<<1] ^ sego[v<<1|1];
} 

void update2(int p, int v, int nod, int l, int r){
	if(l == r){
		sego[nod] = v;
		b[p] = v;
		return;
	}
	int m = (l+r)>>1;
	if(p <= m) update2(p, v, nod<<1, l, m);
	else update2(p, v, nod<<1|1, m+1, r);

	sego[nod] = sego[nod<<1] ^ sego[nod<<1|1];
}

int query2(int l, int r, int nod, int tl, int tr){
	if(tl > r || tr < l || tl > tr) return 0;
	if(tl >= l && tr <= r){
		return sego[nod];
	}

	int m = (tl+tr)>>1;
	return query2(l, r, nod<<1, tl, m) ^ query2(l, r, nod<<1|1, m+1, tr);
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	vector<int> nz(n+1);
	for(int i = 1; i <= n; i++) cin >> nz[i];
	for(int i = 1; i <= n; i++){
		if(i % 2 == 0) a[i] = nz[i];
		else b[i] = nz[i];
	}
	build(1, 1, n);
	build2(1, 1, n);

	for(int i = 0; i < q; i++){
		int t; cin >> t;
		if(t == 1){
			int p, v; cin >> p >> v;
			if(p % 2 == 0) update(p, v, 1, 1, n);
			else update2(p, v, 1, 1, n);
		}
		else{
			int l, r; cin >> l >> r;
			if((r - l + 1) % 2 == 0) cout << "0\n";
			else if(l % 2 == 0) cout << query(l, r, 1, 1, n) << '\n';
			else cout << query2(l, r, 1, 1, n) << '\n';
		}
	}
	return 0;
}

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