BOJ 16713 - Generic Queries 링크
(2023.10.12 기준 S2)

문제

길이가 N인 수열 a가 주어진다.
Q개의 쿼리 s, e가 주어지는데, 쿼리의 결과는 [s, e] 구간에 있는 ai를 모두 XOR한 값이다.

모든 쿼리의 답을 XOR한 결과 출력

알고리즘

누적 합

풀이

배타적 논리합은 교환법칙, 결합법칙이 성립한다.

그러므로 구간 a~b의 값을 XOR한 값을 [a, b]라고 나타낼 때,

[s, e] ≡ [1, s-1] ⊕ [s, e] ⊕ [1, s-1]
≡ ([1, s-1] ⊕ [s, e]) ⊕ [1, s-1]
≡ [1, e] ⊕ [1, s-1]

[1, e]와 [1, s-1]은 누적 배타적 논리합 배열을 만들어 놓으면 O(1)에 구할 수 있다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, Q; cin >> N >> Q;
    int a[N + 1]; for (int i = 1; i <= N; i++) cin >> a[i];

    // 누적 배타적 논리합 배열 만들기
    int prefix_xor[N + 1]; prefix_xor[0] = 0;
    for (int i = 1; i <= N; i++) prefix_xor[i] = prefix_xor[i - 1] ^ a[i];

    // 배타적 논리합은 교환법칙과 결합법칙이 성립하므로
    // 구간 xor [s, e] = 누적 xor [e] ⊕ 누적 xor [s - 1]
    int result = 0;
    for (int s, e; Q; Q--){
        cin >> s >> e;
        result ^= prefix_xor[e] ^ prefix_xor[s - 1];
    }

    cout << result;
}

• Python

import sys; input = sys.stdin.readline

N, Q = map(int, input().split())
a = list(map(int, input().split()))

# 누적 배타적 논리합 배열 만들기
prefix_xor = [0] * (N + 1)
for i in range(1, N + 1):
    prefix_xor[i] = prefix_xor[i - 1] ^ a[i - 1]

# 배타적 논리합은 교환법칙과 결합법칙이 성립하므로
# 구간 xor [s, e] = 누적 xor [e] ⊕ 누적 xor [s - 1]
result = 0
for _ in range(Q):
    s, e = map(int, input().split())
    result ^= prefix_xor[e] ^ prefix_xor[s - 1]

print(result)