lazy propagation

백준 1395번 - 스위치

https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net # Approach) 선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자. 해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다. # Time Complexity) 업데이트를 진행할때 s~t구간의 스위치를 모두 토글해야한다. 각 원소를 하나하나 토글한다면 세그먼트 트리를 사용했을때 시간복잡도는최대 한번의 업데이트에 $O(log(n))$으로 전체의 쿼리에 ..