Koala - 11기/코딩테스트 준비 스터디
[C++] 백준 16713번: Generic Queries
luciduskim
2023. 8. 5. 20:01
https://www.acmicpc.net/problem/16713
16713번: Generic Queries
첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$) 둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$) 그 후, $Q$개의 줄에 걸
www.acmicpc.net
1. 문제풀이
누적합 문제를 XOR 연산을 적용하여 만든 문제이다. XOR 연산은 교환법칙과 결합법칙이 성립한다. 양수 A가 있을 때 XOR 연산은 다음이 성립한다.
1. A XOR 0 = A (0은 항등원)
2. A XOR A = 0 (A는 역원)
위 식이 성립할 때, s번째 값부터 e번째 값까지 XOR 연산을 누적합 연산과 같이 풀어써보면 다음과 같음을 알 수 있다. (s = 2, e = 4라고 가정)
(V[0] XOR V[1] XOR V[2] XOR V[3] XOR V[4]) XOR (V[0] XOR V[1])
= {(V[0] XOR V[1]) XOR (V[0] XOR V[1])} XOR (V[2] XOR V[3] XOR V[4])
= 0 XOR (V[2] XOR V[3] XOR V[4])
= V[2] XOR V[3] XOR V[4]
2. C++ 코드
#include <iostream>
#include <stdio.h>
using namespace std;
int prefix[(int)1e6 + 1];
int main(void)
{
int n, q, tmp, s, e, res = 0;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &tmp);
prefix[i] = prefix[i - 1] ^ tmp;
}
while (q--) {
scanf("%d %d", &s, &e);
res ^= (prefix[e] ^ prefix[s - 1]);
}
printf("%d\n", res);
return 0;
}