[백준 12844번] XOR

---

12844번: XOR

---

 

목차

• 사전 지식
• 문제 풀이

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있어야 한다. (링크)

 

 

 

문제 풀이

전형적인 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)에 관한 문제이다.

느리게 갱신되는 세그먼트 트리를 구현할 때는 다음과 같은 질문에 답을 해야 한다.

• 구간 단위로 업데이트할 때 대응하는 노드에는 어떤 변화가 일어나는가
• propagate()를 할 때 어떤 일이 발생하는 가

 

이 문제를 풀기 전에 알아야 할 사실은 어떤 수 $x$에 $k$를 짝수번 xor하면 $x$라는 사실이다.

이러한 사실을 이용하여 위의 질문에 대한 답을 찾아보자.

 

구간 단위로 업데이트할 때 대응하는 노드에는 어떤 변화가 일어나는가

어떤 노드는 해당 구간에 있는 원소들을 xor한 값을 가지고 있다.
그리고 세그먼트 트리의 (리프 노드를 제외한)노드는 짝수개의 원소에 대응한다.
따라서, (리프 노드를 제외한)노드의 값은 변하지 않으므로 아무 일도 일어나지 않는다.

 

propagate()를 할 때 어떤 일이 발생하는가

propagate()의 일반적인 방식은 현재 노드를 갱신하며 자식 노드로 전파하는 방식이다.
하지만, 이 문제에서는 현재 노드를 갱신하는 것이 원래와 같으므로 자식 노드로 전파만 해주면 된다.
단, 리프 노드는 한 개(홀수개)의 원소이므로 갱신을 시켜줘야 한다.