[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 8291번: Coprime Numbers  (0) 2020.02.25
[BOJ] 12107번: 약수 지우기 게임 1  (0) 2020.02.18
[BOJ] 13318번: 위험한 해싱  (0) 2020.02.01
[BOJ] 1933번: 스카이라인  (1) 2019.12.03
[BOJ] 10167번: 금광  (0) 2019.12.02
[BOJ] 15293번: Knapsack Cryptosystem  (0) 2019.10.21
  Comments