[BOJ] 백준 3653번: 영화 수집

영화 수집

문제

쿼리마다 i 번째 영화 위에 쌓여있는 다른 영화의 수를 출력하는 문제이다.

문제 풀이

naive하게 쿼리마다 현재 영화보다 위에 있는 영화를 카운트하는 방식으로는 \(O(NM)\) 이라 불가능하고, 힌트로는 영화를 꺼냈을 때 그 부분이 밀쳐지지 않고 비워진다는 방식으로 이해한다는 것이다. 그리고 영화를 꺼내면 맨 위에 차곡차곡 쌓는다. 그래서 현재 i층에 영화가 존재하는지, 안 하는지를 저장하는 \(check[i]\)을 생각해 보자.

index	value
0	0
1	0
2	0
....	..
m	1
m+1	1
m+2	1
...	...
m+n-1	1

초기의 \(check[i]\)값은 위와 같다. 여기에 현재 i번째 영화가 어디 있는지에 대한 \(idx[i]\) 배열을 만들어 준다. 초기에는 \(idx[i]=m+i\)값이 들어가게 된다.

여기서 쿼리로 k번 째 영화를 찾는다면 \(\sum_{i=0}^{idx[k-1]} {check[i]}\) 값을 출력하고 \(check[idx[k]]\) 값을 0으로 그리고 맨 위에 해당하는 위치에 check[i]를 1로 바꿔주면 된다. 여기서 구간 합을 구하기 위해서 팬윅트리를 이용하면 된다.

\(O(MlgN)\)

 

소스 코드