[백준/Python] 16713번: Generic Queries

문제

 

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

---

Algorithm

누적합

누적합이 아니라 매번 모든 쿼리를 계산하면 시간 초과가 난다.
또한 베타적 논리합(XOR, ⊻)이 결합법칙이 성립함을 알고 있어야 한다.
예를 들어 (a1 ⊻ a2 ⊻... a10) = (a1 ⊻ a2) ⊻ (a3 ⊻ a4 ⊻ ... a10) 이다.
그리고 A ⊻ B = C 일 때, C ⊻ A = B, C ⊻  B = A 이다.
추가적으로 0 ⊻ N = N 임을 알고 있어도 도움이 된다.

 

---

 

 

Code

input = __import__('sys').stdin.readline

N, Q = map(int, input().rstrip().split())
a_list = list(map(int, input().rstrip().split()))
q_list = [list(map(int , input().rstrip().split())) for i in range(Q)]
prefix_Q_lsit = [0] * (N + 1)
result = 0

for i in range(1, N + 1) :
    prefix_Q_lsit[i] = prefix_Q_lsit[i - 1] ^ a_list[i - 1]

for i in q_list :
    result ^= prefix_Q_lsit[i[1]] ^ prefix_Q_lsit[i[0] - 1] 

print(result)

 

느낀 점

오랜만에 논리 연산, 이산 수학 공부의 중요성을 다시 깨달았다. 또한 처음에는 따로 누적합 리스트를 만들지 않고 기존 리스트에서 누적합을 진행했는데, 이러면 예를 들어 1,1 쿼리 같은 경우에서 인덱싱 에러가 발생하기 쉬워 가장 처음에 0을 포함하는 누적합 리스트를 따로 만들어서 진행했다.