[백준 / BOJ] 1395 스위치

문제

1395번: 스위치

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O

www.acmicpc.net

N개의 스위치가 있고 M번의 명령이 주어진다.

명령은 O,S,T의 형태로 주어지는데,

O가 1 이라면, S부터 T까지 켜져있는 전구의 갯수를 구하는 명령이고,

O가 0이면, S부터 T까지의 전구의 상태를 반전시키는 명령이다.

구간 합 구하기 2와 비슷하게 풀리는 문제였다.

N이 10만, M이 10만이므로, 한번 업데이트시 최악의경우 10만log10만번 반복해서 시간초과가 난다. (세그먼트 트리의 가장 하위노드까지 들어가야하므로)

lazy propagation을 사용해서 풀면된다.

layz propagation이란, 현재 노드의 하위노드들에 대해서, 지금 당장 업데이트 해줄 필요가없으면, 저장만 해놓고 나중에 필요할때(혹은 해당 노드를 지나가야할때) 업데이트하는 방식을 말한다.

세그 트리에 켜진전구의 갯수를 저장하며 풀면된다.

해당 범위의 스위치를 누른횟수(lazy배열에 저장된 값)가 홀수라면, 전구를 반전시키고, 아니라면 반전시키지않는다.

devxb/JJUNalgo

백준 알고리즘 소스코드🙃. Contribute to devxb/JJUNalgo development by creating an account on GitHub.

github.com