문제 링크
https://www.acmicpc.net/problem/14427
풀이
${A_i, i}$를 관리하는 최솟값 세그 트리를 구현해 주면 됩니다. 하지만 전체 구간에 대한 쿼리로 주어지므로 set이나 삭제가 가능한 우선순위큐를 이용해 최솟값만 가져올 수 있도록 구현해도 됩니다. 업데이트 $O(\log N)$, 쿼리 $O(1)$이므로 전체 시간복잡도는 $O(M \log N)$입니다. 아래는 삭제가 가능한 우선순위큐로 구현한 코드입니다.
전체 코드
1 |
|