multiset의 $O(1)$은 다른 자료구조의 $O(1)$과 다르다

본론

multiset을 사용하게 되는 문제들 중 $O(1)$을 써야하는 문제가 있다. 원소 x에 접근은 상수시간이 걸리는데, 문제를 풀다보면 이 상수시간에 걸려 TLE가 나는 경우가 종종있다.

set 종류가 빠른 자료구조이고 접근도 용이하지만, 내부에 자료 양이 많아ㅏ진다면 그만큼 접근 속도도 느려지게 된다.

이를 해결하기 위해서는 priority_queue를 이용하여 set을 대체할수 있다.

set을 priority_queue로 대체하는 방법

상수시간과 관련된 내용은 상수커팅과 관련되있으므로, 해당 관련 게시글들을 찾아보면 좋을 것이다.