(BOJ12844 XOR

• tags : (algorithm

  No matching post could be found

• 문제 링크 : https://www.acmicpc.net/problem/12844
• 풀이 링크
  • Python

• lazy propagation을 필요하지만, 문제 해결을 위한 추가적인 문제 해결 전략이 필요하다.
• 전반적인 코드는 (백준 10999 구간 합 구하기 2

  No matching post could be found

  와 같다.
  • 차이점은 연산이 더하기가 아니라 XOR인 부분이다.
  • 이 글에서도 해당 부분만 다루어 문제 풀이를 작성할 것이다.

• 처음에는 연산은 더하기에서 XOR로 변경했는데, 문제 해결이 잘 되지 않았다.
  • 여기서 XOR의 특징을 생각해보면 그 답을 알 수 있다.
  • XOR은 교환법칙이 성립하고,
  • 어떤 수와 0을 XOR하면 그 수가 나오게 되고, 같은 수를 XOR하면 0이 된다.
  • 그래서 lazy를 적용할 때, 같은 수가 몇 번 XOR 되는지 생각하면 된다.

def update_lazy(self, node: int, start: int, end: int) -> None:
    if self.lazy[node]:
        if (end - start + 1) % 2:
            self.tree[node] ^= self.lazy[node]
        if start != end:
            self.lazy[node * 2] ^= self.lazy[node]
            self.lazy[node * 2 + 1] ^= self.lazy[node]
        self.lazy[node] = 0

def update_range(
    self, node: int, start: int, end: int, left: int, right: int, k: int
) -> None:
    self.update_lazy(node, start, end)
    if right < start or end < left:
        return
    if left <= start and end <= right:
        if (end - start + 1) % 2:
            self.tree[node] ^= k
        if start != end:
            self.lazy[node * 2] ^= k
            self.lazy[node * 2 + 1] ^= k
        return
    mid = self.mid(start, end)
    self.update_range(node * 2, start, mid, left, right, k)
    self.update_range(node * 2 + 1, mid + 1, end, left, right, k)
    self.tree[node] = self.tree[node * 2] ^ self.tree[node * 2 + 1]

• 다른 메서드는 같이 작성되어 있는데, 이 두 메서드만 일부 수정되었다.
• 위의 방식을 생각하여, 어떤 수가 XOR이 몇 번 적용되는지, 특히 홀수 번 적용될때만 특정 위치마다 값을 갱신하고, 아니면 넘어가는 방식으로 구현했다.