제출 #929257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
929257		Chinguun	XORanges (eJOI19_xoranges)	C++14	100 / 100	104 ms	14912 KiB

xoranges

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

#define int long long
#define ff first
#define ss second
#define pb push_back
#define meta int x = i * 2 + 1, y = x + 1, m = (L + R) / 2

const int N = 2e5 + 7;
const int oo = 1e18;
const int mod = 1e9 + 7;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

int n, q, n1, n2, a, c, l, r, x[N], y[N];
int s1[N * 4], s2[N * 4];

void build1(int i, int L, int R) {
	if(L == R) {
		s1[i] = x[L];
		return;
	}
	meta;
	build1(x, L, m);
	build1(y, m + 1, R);
	s1[i] = (s1[x] ^ s1[y]);
	return;
}

void build2(int i, int L, int R) {
	if(L == R) {
		s2[i] = y[L];
		return;
	}
	meta;
	build2(x, L, m);
	build2(y, m + 1, R);
	s2[i] = (s2[x] ^ s2[y]);
	return;
}

int query1(int i, int L, int R, int l, int r) {
	if(L == l && r == R) return s1[i];
	meta;
	if(r <= m) return query1(x, L, m, l, r);
	if(m + 1 <= l) return query1(y, m + 1, R, l, r);
	return (query1(x, L, m, l, m) ^ query1(y, m + 1, R, m + 1, r));
}

int query2(int i, int L, int R, int l, int r) {
	if(L == l && r == R) return s2[i];
	meta;
	if(r <= m) return query2(x, L, m, l, r);
	if(m + 1 <= l) return query2(y, m + 1, R, l, r);
	return (query2(x, L, m, l, m) ^ query2(y, m + 1, R, m + 1, r));
}

void update1(int i, int L, int R, int k, int v) {
	if(L == R) {
		s1[i] = v;
		return;
	}
	meta;
	if(k <= m) update1(x, L, m, k, v);
	else if(k > m) update1(y, m + 1, R, k, v);
	s1[i] = (s1[x] ^ s1[y]);
	return;
}

void update2(int i, int L, int R, int k, int v) {
	if(L == R) {
		s2[i] = v;
		return;
	}
	meta;
	if(k <= m) update2(x, L, m, k, v);
	else if(k > m) update2(y, m + 1, R, k, v);
	s2[i] = (s2[x] ^ s2[y]);
	return;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
//	cout << "=======================\n";
	cin >> n >> q;
	n2 = n / 2;
	n1 = n - n2;
	for(int i = 1; i <= n; i++) {
		cin >> a;
		if(i % 2 == 1) x[i / 2] = a;
		else y[(i / 2) - 1] = a;
	}
	build1(0, 0, n1 - 1);
	build2(0, 0, n2 - 1);
	while(q--) {
		cin >> c >> l >> r;
		l--; r--;
		if(c == 1) {
			if(l % 2 == 0) update1(0, 0, n1 - 1, l / 2, r + 1);
			else update2(0, 0, n2 - 1, l / 2, r + 1);
		}
		else {
			if((r - l + 1) % 2 == 0) cout << "0\n";
			else {
				if(l % 2 == 0) cout << query1(0, 0, n1 - 1, l / 2, r / 2) << '\n';
				else cout << query2(0, 0, n2 - 1, l / 2, r / 2) << '\n';
			}
		}
	}
	return 0;
}

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