Submission #1241065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241065		azamurai	XORanges (eJOI19_xoranges)	C++20	100 / 100	93 ms	11336 KiB

xoranges

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define Sz(x) (int)x.size()
#define mp make_pair

using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
int n, q, a[N];

struct seg_tree {
	int t[N*4];
	void upd(int v, int tl, int tr, int pos, int x) {
		if (tl == tr) {
			t[v] = x;
			return;
		}
		int mid = (tl + tr) / 2;
		if (pos <= mid) upd(v+v,tl,mid,pos,x);
		else upd(v+v+1,mid+1,tr,pos,x);
		t[v] = (t[v+v] ^ t[v+v+1]);
	} 
	int get(int v, int tl, int tr, int l, int r) {
		if (tl > r || l > tr) return 0;
		if (tl >= l && tr <= r) return t[v];
		int mid = (tl + tr) / 2;
		return (get(v+v,tl,mid,l,r) ^ get(v+v+1,mid+1,tr,l,r));
	}
} rt1, rt2;

void solve() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (i % 2 == 1) rt1.upd(1,1,n,i,a[i]);
		else rt2.upd(1,1,n,i,a[i]);
	}
	while (q--) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int ind, val;
			cin >> ind >> val;
			if (ind % 2 == 1) rt1.upd(1,1,n,ind,val);
			else rt2.upd(1,1,n,ind,val);
			a[ind] = val;
		}
		else {
			int l, r;
			cin >> l >> r;
			if ((r - l + 1) % 2 == 0) cout << 0 << '\n';
			else {
				if (l % 2 == 1) cout << rt1.get(1,1,n,l,r) << '\n';
				else cout << rt2.get(1,1,n,l,r) << '\n';
			}
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	int t = 1;
	//cin >> t;
	while ( t-- ) {
		solve();
		cout << '\n';
	}
}

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