백준 16713: Generic Queries

문제 요약

관영이는 쿼리를 좋아하고, XOR도 좋아한다. 그래서 관영이는 XOR을 이용한 쿼리 문제를 좋아한다.

길이가 $N$인 수열 $a_1 , a_2 , \cdots a_N$이 있다.

이제 관영이는
$Q$개의 쿼리에 답하려 한다. 각 쿼리는 $s_i , e_i$ ($1 \le s_i \le e_i \le N$)의 형태로 들어오고, 그 쿼리의 답은 $a_{s_i}, a_{s_i+1}, \cdots a_{e_i}$을 모두 XOR한 값이다.

$Q$개의 쿼리가 들어올 때, 각 쿼리의 답을 모두 XOR한 결과를 구하시오.

문제 분류

• 누적 합

문제 풀이

누적합의 연산자가 반드시 합이 아니어도 된다. 보통의 누적합 알고리즘은 S[i] = S[i - 1] + K의 식이 되지만, 이러한 문제의 경우 S[i] = S[i - 1] ^ K로, XOR연산자를 넣어주어야 한다.

답을 구할 때에도 S[e] - S[s] 가 아닌, S[e] ^ S[s]를 res에 XOR을 시켜주어야 한다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

int S[1000001];

int main() {
	int n, q, in, in2;
	int res = 0;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &in);
		S[i] = S[i - 1] ^ in;
	}
	while (q--) {
		scanf("%d%d", &in, &in2);
		res ^= S[in2] ^ S[in - 1];
	}
	printf("%d", res);
	return 0;
}