[백준 19588] 상품권 준비

문제

www.acmicpc.net/problem/19588

19588번: 상품권 준비

 

문제 풀이

쿼리마다 계산한다면 $O(a*M*Q)$로 TLE가 난다.

이에 누적xor배열을 만들어 pxor[b+am]-pxor[b]꼴의 형태로 답을 내려했으나 누적합과 달리 xor연산에서는 단지 뺀다고 (b + 1) ~ (b + a *m)의 xor연산값이 나오지 않을뿐더러 문제에서는 m개 덩어리만큼씩 xor한 합을 구해야했다.

고민해봐도 모르겠길래 해설을 보니 x ⊕ x= 0을 이용하여 m개씩 묶음의 xor을 계산했고, 누적합과 비슷하게 dp배열을 사용하여 해결했다.

pxor2[i] = pxor2[i - m] + (pxor[i] ⊕ pxor[i - m]) // pxor2[i] = i를 마지막인덱스로 m개씩 xor한 묶음을 더한 값

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int n, m, x, y, q, a, b;
vector<pll> v;
vector<ll> pxor, pxor2;
bool cmp(pll &a, pll &b) {
	return a.first > b.first;
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	v.resize(n + 1), pxor.resize(n + 1), pxor2.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> x >> y;
		v[i] = { x, y };
	}
	auto it = v.begin();
	sort(it + 1, v.end(), cmp);
	for (int i = 1; i <= n; i++)
		pxor[i] = (v[i].second ^ pxor[i - 1]);
	for (int i = 1; i <= n; i++)
		if (i >= m) pxor2[i] = pxor2[i - m] + (pxor[i] ^ pxor[i - m]);
	cin >> q;
	while (q--) {
		cin >> a >> b;
		cout << pxor2[b + a* m] - pxor2[b] << '\n';
	}
}