[BOJ][Python] 백준 3653번 - 영화 수집

문제 링크: https://www.acmicpc.net/problem/3653

---

문제 풀이

세그먼트 트리

 

N+M개의 배열을 생각해서 세그트리를 짜면 된다. 그리고 인덱스 배열을 하나 만들 건데 [0, n, n-1, n-2, ..., 1]로 만들어준다. 그 이유는 1이 가장 위에 있으므로 자신의 위쪽엔 아무것도 없다. 이를 배열로 생각하면 자신의 오른쪽에는 아무것도 없다라는 의미고 아래는 자신의 왼쪽이라고 생각하면 된다. 아무튼 인덱스가 지금 최대 n이니 책을 꺼냈다면 그 책의 인덱스는 이제 n+1이 되고 원래 있었던 인덱스의 세그 값은 0으로, 새롭게 만들어진 인덱스는 1로 업데이트 하면 문제에 대한 쿼리를 적절하게 수행할 수 있다.

 

 

코드