오늘 뭐했지

https://boj.ma/17943/t

${N}$과 ${Q}$, 그리고 ${N-1}$개의 수가 주어집니다.

${N - 1}$개의 수는

${a_0}$ ${\oplus}$ ${a_1}$, ${a_1}$ ${\oplus}$ ${a_2}$, .... , ${a_{n-1}}$  ${\oplus}$ ${a_n}$ 으로, 입력으로 주어진 i번째 숫자는 원본배열의 i번째 수와 i+1번째 수를 xor한 값입니다.

이후 ${Q}$개의 쿼리가 주어지는데, 쿼리의 종류가 두 가지 있습니다.

0 x y 는 x번째 수와 y번째 수를 xor한 값을 출력하는 쿼리이고,

1 x y d는 x번째 수가 d일때, y번째 수를 출력하라는 쿼리입니다.

xor문제에서는 항상 xor의 중요한 특성 두 가지를 떠올리면 풀리는 경우가 많습니다.

${0}$ ${\oplus}$ ${X}$ = ${X}$

${X}$ ${\oplus}$ ${X}$ = ${0}$

이 두가지 xor연산의 특징을 바탕으로 생각을 해봅니다.

0번 쿼리인 x번째 수와 y번째 수를 xor한 값의 결과는

주어진 배열에서

${A_x}$ ${\oplus}$ ${A_{x+1}}$ ${\oplus}$ ${A_{x+1}}$ ${\oplus}$ ${A_{x+2}}$  ${\oplus}$ ${...}$ ${\oplus}$ ${A_{y-2}}$ ${\oplus}$ ${A_{y-1}}$ ${\oplus}$  ${A_{y-1}}$ ${\oplus}$ ${A_y}$ 를 해주면 중간 항이 모두 소거되기 때문에

${A_x}$ ${\oplus}$ ${A_y}$ 와 같습니다.

따라서 입력으로 주어진 배열에서 x번째 수부터 y - 1번째 수까지 xor한 값을 출력해주면 됩니다.

1번 쿼리는

${X}$번째 수가 ${d}$일때 ${Y}$번째 수를 출력하는 것인데, ${A_X}$ ${\oplus}$ ${A_Y}$ ${\oplus}$ ${A_X}$ ${=}$ ${A_Y}$ 이므로

0번 쿼리를 그대로 갖고온 결과에 ${d}$ 를 xor 해주면 됩니다.

당연히 쿼리마다 일일히 xor해주면 시간초과이므로, 누적합 배열을 이용해 전처리 해주면 쿼리마다 ${O(1)}$ 에 값을 구할 수 있습니다.

코드(python)

import sys
input = sys.stdin.readline


n, q = map(int, input().split())
ls = [0] + list(map(int, input().split()))
k = len(ls)
pxor = [0] * (k)
for i in range(1, k):
    pxor[i] = pxor[i- 1] ^ ls[i]
for _ in range(q):
    oper, *a = map(int, input().split())
    if oper:
        x, y, d = a
        print(pxor[y - 1] ^ pxor[x - 1] ^ d)
    else:
        x, y = a
        print(pxor[y - 1] ^ pxor[x - 1])