[백준/12844] XOR (Python)

Problem : https://www.acmicpc.net/problem/12844

12844번: XOR

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:18:56

 

---

 

문제 설명

 

 

크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자.

1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다.
2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 수열의 크기 N이 주어진다.

두 번째 줄에는 A0, A1, ..., AN-1이 차례대로 주어지며, 공백 한 칸으로 구분되어져 있다.

세 번째 줄에는 쿼리의 개수 M이 주어지고, 다음 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

 

출력

 

2번 쿼리의 결과를 모두 출력한다.

 

입력 예시

 

5
1 2 3 4 5
3
2 0 4
1 2 4 9
2 0 4

 

출력 예시

 

1
8

 

 

---

 

풀이

 

XOR의 특성을 고려해보도록 하자.

 

• XOR 연산은 결합법칙이 성립한다. 즉 임의의 구간 [start, mid]와 [mid+1, end] 간의 xor 연산을 하나씩 순차적으로 처리하거나, 혹은 구간끼리 먼저 연산을 수행하고 마지막에 두 결과를 xor연산하는 경우 둘 모두 동일한 결과를 가져온다. 또한 임의의 lazy[idx]에 다른 xor연산이 추가된다면, lazy[idx]에 바로 이를 반영할 수 있다.
• XOR 연산을 자기 자신에게 수행할 경우 결과값은 무조건 0이다. 즉 lazy[idx]를 tree[idx]에 반영할 때, 이 점을 이용할 수 있겠다. idx가 [start, end]구간을 가리키는 인덱스라고 가정할 때, 이 때 범위 내의 수가 (end - start + 1)가 된다.
  (a_start ^ lazy[idx]) ^ (...) ^ (a_end ^ lazy[idx]) = (a_start) ^ (...) ^ (a_end) ^ (lazy[idx]) ^ (...) ^ (lazy[idx]) 가 되므로, 이는 최종적으로 원래 tree[idx]값에 lazy[idx]를 xor하는 연산을 (end - start + 1) 반복하는 연산과 동일하다. 즉 이 (end - start + 1) % 2 == 1이라면 lazy[idx]를 한 번 xor하고, 그렇지 않다면 원래 tree값이 그대로 보존된다.

이런 특성을 통해 lazy segment tree를 사용하여 바로 구현해 볼 수 있는 문제이다.

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
num_list = list(map(int, input().split()))

class LazySegTree :
  def __init__(self) :
    self.tree = [0]*(4*N)
    self.lazy = [0]*(4*N)
    def _init(start, end, idx) :
      if start == end :
        self.tree[idx] = num_list[start]
        return
      mid = (start + end) // 2
      _init(start, mid, idx*2)
      _init(mid+1, end, idx*2+1)
      self.tree[idx] = self.tree[idx*2]^self.tree[idx*2+1]

    _init(0, N-1, 1)

  def propagate(self, start, end, idx) :
    if start < end :
      self.lazy[idx*2] ^= self.lazy[idx]
      self.lazy[idx*2+1] ^= self.lazy[idx]
    if (end - start + 1) % 2 :
      self.tree[idx] ^= self.lazy[idx]
    self.lazy[idx] = 0

  def update(self, left, right, val) :
    def _update(start, end, idx) :
      self.propagate(start, end, idx)
      if right < start or left > end :
        return
      if left <= start <= end <= right :
        self.lazy[idx] ^= val
        self.propagate(start, end, idx)
        return
      mid = (start + end) // 2
      _update(start, mid, idx*2)
      _update(mid+1, end, idx*2+1)
      self.tree[idx] = self.tree[idx*2]^self.tree[idx*2+1]

    _update(0, N-1, 1)

  def search(self, left, right) :
    def _search(start, end, idx) :
      self.propagate(start, end, idx)
      if right < start or left > end :
        return 0
      if left <= start <= end <= right :
        return self.tree[idx]
      mid = (start + end) // 2
      result = 0
      result ^= _search(start, mid, idx*2)
      result ^= _search(mid+1, end, idx*2+1)
      return result

    print(_search(0, N-1, 1))

segtree = LazySegTree()
for _ in range(int(input())) :
  q, *cmd = map(int, input().split())
  if q == 1 :
    i, j, k = cmd
    segtree.update(i, j, k)
  else :
    i, j = cmd
    segtree.search(i, j)

풀이 완료!