[백준/C++] 16713번: Generic Queries

https://www.acmicpc.net/problem/16713

16713번: Generic Queries

누적합(prefix sum)알고리즘을 사용해서 O(N)시간에 답을 구하는 것이 핵심인것 같습니다.

다만 더하기(+) 연산 대신 XOR(^) 연산을 사용해서 문제를 풀어야합니다.

전체적인 알고리즘 흐름은 "11659번: 구간 합 구하기4" 문제와 비슷합니다.

1. 누적 XOR 배열을 선언하고 입력받은 수열의 누적 XOR 값을 저장합니다.
2. 입력받는 Q개의 s, e 쌍 마다 계산해놓은 누적 XOR 배열을 사용해서 "누적XOR[e] ^ 누적XOR[s-1]" 값을 결과로 저장합니다.
3. 최종적으로 Q개의 결과값들을 XOR연산한 값을 출력합니다

 

#include <iostream>
#include <vector>

using namespace std;

int N, Q;
vector<int> V;
vector<int> x_or;
vector<int> result;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> Q;
	V.resize(N + 1);
	x_or.resize(N + 1);
	for (int i = 1; i <= N; i++) cin >> V[i];
	x_or[0] = 0;
	x_or[1] = V[1];
	for (int i = 2; i <= N; i++) {
		x_or[i] = x_or[i - 1] ^ V[i];
	}
	for (int m = 1; m <= Q; m++) {
		int i, j;
		cin >> i >> j;
		result.push_back(x_or[j] ^ x_or[i - 1]);
	}
	int answer = 0;
	for (int i = 0; i < Q; i++) {
		answer = answer ^ result[i];
	}
	cout << answer;
}

 

문제를 풀면서 XOR에 대한 성질들을 공부한 참고 블로그입니다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=oidoman&logNo=221145674383