Submission #1124983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124983		heey	XORanges (eJOI19_xoranges)	C++20	12 / 100	1095 ms	3140 KiB

xoranges

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

const int maxn = 2e5 + 5;
int n;
int seg[4*maxn];
int a[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);
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	for(int i = 0; i < q; i++){
		int t; cin >> t;
		if(t == 1){
			int p, v; cin >> p >> v;
			update(p, v, 1, 1, n);
		}
		else{
			int l, r; cin >> l >> r;
			int ans = 0;
			for(int i = 0; i < r-l+1; i++){
				for(int j = l; j < r-i+1; j++){
					ans ^= query(j, j+i, 1, 1, n);
				}
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

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