제출 #447271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447271		bigo	XORanges (eJOI19_xoranges)	C++14	100 / 100	764 ms	31548 KiB

xoranges

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
struct Seg {
	ll val = INF;
	ll l, r, mid; // responisble for [l,r)
	Seg* lp, * rp;
	Seg(ll l, ll r) : l(l), r(r), mid((l + r) / 2) {
		if (l + 1 < r) {
			lp = new Seg(l, mid);
			rp = new Seg(mid, r);
		}
	}
	void pull() {
		val = lp->val ^ rp->val;
	}
	void update(ll i, ll x) {
		if (l + 1 == r) {
			val = x;
			return;
		}
		if (i < mid) lp->update(i, x);
		else rp->update(i, x);
		pull();
	}
	ll query(ll a, ll b) { // xor of [a,b)
		if (a >= r || b <= l) return 0; // [a,b) and [l,r) are disjoll
		if (a <= l && r <= b) return val; // [l,r) is inside [a,b)
		return lp->query(a, b) ^ rp->query(a, b);
	}
};
int main() {
	ll n, q;
	cin >> n >> q;
	Seg seg(0, n / 2 + 1);
	Seg seg1(0, n / 2 + 1);
	ll g;
	for (ll i = 0; i < n; i++) {
		cin >> g;
		if ((i + 1) % 2 == 1) {
			seg1.update(i / 2, g);
		}
		else
			seg.update(i / 2, g);
	}
	while (q--) {
		ll op;
		cin >> op;
		if (op == 1) {
			ll i, j;
			cin >> i >> j;
			i--;
			if ((i + 1) % 2 == 1)
				seg1.update(i / 2, j);
			else
				seg.update(i / 2, j);
		}
		else {
			ll l, r;
			cin >> l >> r;
			l--, r--;
			if ((r - l + 1) % 2 == 0)
				cout << 0 << endl;
			else {
				if ((l + 1) % 2 == 1) {
					cout << seg1.query(l / 2, r / 2 + 1) << endl;
				}
				else {
					cout << seg.query(l / 2, r / 2 + 1) << endl;
				}
			}
		}
	}
}

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