1. 정렬된 상태의 deque를 관리하면 O(1)에 됨
2. bbst 쓰면 걍 로그 됨 O(1) 되는지는 모르겠음
분할상환 허용하면 O(1)도 될거같음: splay tree같이 split이 지원되는 bbst를 씀. 그리고 2번/3번 쿼리가 주어지면 실제로 값을 삭제하지 말고 최댓값/최솟값을 가리키는 포인터를 옮김. 그리고 1번 쿼리가 주어지면 최대/최소 포인터가 가리키는 지점까지 트리를 자름. splay tree를 썼으니까 이 과정은 O(logN)밖에 안걸림. 그리고 최솟값부터 포인터를 k번 옮기는 데 걸리는 총 시간은 O(트리의 높이+k) \in O(logN+k)임. 1번 쿼리가 주어지고 나면 최대/최소 포인터가 다시 초기화되므로 여기서 logN은 1번 쿼리에 걸리는 시간에 합치고, 남은 k를 k개 2번 쿼리가 나눠 가지면 amortized O(1)이 됨.
3. strict fibonacci heap을 최대 최소 두개 만듬. 최대 힙에는 자기랑 key가 같은 최소 힙의 노드 주소를 저장해둠. 반대로도 마찬가지. 2번 쿼리 주어지면 최대 힙에서 최댓값 삭제하고 저장해둔 주소를 타고 최소 힙에서도 대응하는 노드 삭제하면 O(logN). 이거보다 빨리 하면 정렬을 O(NlogN)보다 빨리 할 수 있어서 불가능함
(위키에서 strict fibonacci heap은 amortized 안하고 삽입 O(1)에 / decrease key O(logN)에 된다카는데 공부해 본적은 없어서 확실하진 않음. 근데 머 맞겠지)