[백준 1395번] 스위치

---

1395번: 스위치

---

 

목차

• 사전 지식
• 문제 풀이

 

 

사전 지식

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

 

 

 

문제 풀이

구간 단위로 업데이트가 일어나므로 느리게 갱신되는 세그먼트 트리를 이용하면 된다.

 

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

어떤 노드는 해당 구간에 켜져 있는 원소들의 개수를 저장하고 있다.
구간에 있는 원소들을 반전시키면 켜져 있는 원소들의 개수는 다음과 같이 변한다.
바뀐 값 = 구간의 크기 - 원래 값

 

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

propagate()는 현재 노드의 정보를 자식 노드에게 전달하는 과정이다.
어떤 구간 연산을 홀수번하면 그대로이고, 짝수번하면 바뀐다.
즉, 넘겨줘야 하는 값은 그 구간의 변화가 홀수번인지, 짝수번인지에 대한 정보만 전달해 주면 된다.