[BOJ] 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리

https://www.acmicpc.net/problem/16977

 

톡방에서 계속 얘기가 나오길래 뭔가 싶어서 풀어봤습니다.

 

어떻게 한번에 맞춘건가 신기할 정도로 구현이 끔찍하게 까다로웠습니다.

 

일단 주어진 문제를 결정 문제로 만들어 parametric search가 가능하다는 사실을 알아내야 하고, 각 쿼리에 대해 작은 시간복잡도로 가능한지 아닌지 판단하기 위해 금광 문제를 풀 때 쓰였던 것과 비슷한 느낌의 lmax, rmax, allmax가 여기서도 쓰입니다.

 

오프라인 쿼리로 만들어 Parallel Binary Search로 할 수도 있고, 그냥 Persistent Segment Tree로 해결할 수도 있습니다. 저는 PST를 이용했습니다.

 

여담이지만 solved.ac를 비교적 최근에 설치했는데 정말 좋은 프로그램이네요.. shiftpsh님 만쉐이

 

https://github.com/blisstoner/BOJ/blob/master/16977.cpp