Submission #578729

#	Time	Username	Problem	Language	Result	Execution time	Memory
578729		kideso	XORanges (eJOI19_xoranges)	C++17	0 / 100	633 ms	14076 KiB

xoranges

#include <iostream>
#include <queue>
#include <fstream>

using namespace std;

vector<int> x;

struct Stree {
	vector<int> st;

	void Init(int N) {
		st.assign(4 * N + 1, 0);
	}

	void Build(int p, int l, int r, int k) {
		if (l == r) {
			st[p] = x[2 * l + k];
			return;
		}

		int m = (l + r) / 2;
		Build(2 * p, l, m, k); Build(2 * p + 1, m + 1, r, k);

		st[p] = st[2 * p] ^ st[2 * p + 1];
	}

	void Update(int p, int l, int r, int i, int k) {
		if (l == r) {
			st[p] = x[2 * l + k];
			return;
		}

		int m = (l + r) / 2;
		if (i <= m) Update(2 * p, l, m, i, k);
		else Update(2 * p + 1, m + 1, r, i, k);

		st[p] = st[2 * p] ^ st[2 * p + 1];
	}

	int Query(int p, int l, int r, int a, int b, int k) {
		if (a <= 2 * l + k && 2 * r + k <= b) return st[p];

		if (a > 2 * r + k || b < 2 * l + k) return 0;

		int m = (l + r) / 2;
		return Query(2 * p, l, m, a, b, k) ^ Query(2 * p + 1, m + 1, r, a, b, k);
	}
};

int main()
{
	//ifstream F("be.txt");
	int N, Q;
	cin >> N >> Q;

	x.assign(N + 2, 0);
	for (int i = 1; i <= N; ++i)
		cin >> x[i];

	Stree E, O;
	E.Init(N), O.Init(N);

	E.Build(1, 1, N / 2, 0);
	O.Build(1, 1, N / 2 + 1, -1);


	int c, a, b;
	while (Q--) {
		cin >> c >> a >> b;
		if (c == 1) {
			x[a] = b;
			if (a % 2 == 0) E.Update(1, 1, N / 2, a, 0);
			else O.Update(1, 1, N / 2 + 1, a, -1);
		}
		else {
			if ((b - a + 1) % 2 == 0) {
				int k = (a + b) / 2;
				int e = E.Query(1, 1, N / 2, a, k, 0);
				int o = O.Query(1, 1, N / 2 + 1, k + 1, b, -1);

				cout << (e ^ o);
			}
			else {
				int k = (a + b) / 2;
				if (a % 2 == 0) cout << E.Query(1, 1, N / 2, a, b, 0);
				else cout << O.Query(1, 1, N / 2 + 1, a, b, -1);
			}

			cout << '\n';
		}
	}

	return 0;
}

Compilation message (stderr)

xoranges.cpp: In function 'int main()':
xoranges.cpp:85:9: warning: unused variable 'k' [-Wunused-variable]
   85 |     int k = (a + b) / 2;
      |         ^

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