3653. 영화 수집

오래 전부터 알고만 있던 문제.

3653번: 영화 수집

---

영화의 위치를 추적하는 문제이다. $N$과 $M$이 각각 최대 10만이므로 로그 시간 안에 위치를 찾고 업데이트해야 한다.

 

쿼리를 로그 시간에 수행하는 방법은 여러 가지이지만, 알고 있는 모든 방법을 검토해 보니 세그먼트 트리가 적당해 보인다. 그 중에서도 합 세그먼트 트리를 써 보자.

 

트리에 무엇을 저장할까? 위치를 직접 저장할 수는 없고, 특정 위치에 DVD가 있는지 저장하면 될 것 같다. 이렇게 하면 특정 DVD 앞에 DVD가 몇 개 있는지 계산할 수 있다.

 

이제 업데이트를 구현해 보자. DVD를 맨 위로 옮기는 가장 쉬운 방법은 1) 볼 DVD를 빼고 2) 위에 있는 DVD를 한 칸씩 아래로 내리고 3) 본 DVD를 맨 위에 올리는 것이다. 하지만 이 방법은 $O(N)$이다.

 

애초에 트리의 칸 수를 늘리면 되지 않을까? 리프가 $N+M+1$개인 세그먼트 트리를 만들고, DVD를 처음 쌓을 때 인덱스 $M+1$부터 저장하는 것이다. $i$번째 쿼리에서 본 DVD는 $M-i$번에 저장하면 맨 앞에 저장하는 효과를 낼 수 있다. DVD의 위치는 별도의 배열에 저장하면 된다. 이렇게 하면 로그 시간에 DVD의 위치를 업데이트할 수 있다. 

 

이제 각 쿼리마다 위에서 구현한 연산을 적절히 실행하면 된다.

1. 보려는 DVD 앞에 DVD가 몇 개 있는지 계산한다.
2. DVD를 본다. (이건 상근이에게 구현되어 있다)
3. DVD를 원래 위치에서 뺀다.
4. DVD를 맨 위로 옮긴다.

---

메모리는 많이 써도 되니까 시간만 줄이자.

 

스스로 거의 다 풀 수 있었는데.. 조금만 더 생각할걸. 아깝다.