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

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

16713번: Generic Queries

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;
}