백준 16977 히스토그램에서 가장 큰 직사각형과 쿼리

문제 설명(링크)

www.acmicpc.net/problem/16977

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

문제 요약

[l, r]영역의 직사각형만 사용하여 너비가 w인 직사각형 중 가장 넓이가 큰 것을 출력하는 문제이다.

 

풀이 과정

너비가 정해져 있으므로, 높이가 가장 큰 것이 넓이가 가장 크다. 또, 높이가 h인 직사각형이 존재하면 h-1인 직사각형도 존재하므로, h에 대한 이분탐색을 할 수 있다. 높이가 h인 직사각형이 존재한다는 것의 필요충분조건은 히스토그램에서 연속하게 높이가 h보다 큰 직사각형이 w개 이상 존재하는 것이다.

 

우선, 다음과 같은 간단한 풀이를 생각할 수 있다.

 

각 $h$에 대해, 네 값을 저장하는 세그먼트 트리를 만든다.

 

* 세그트리의 노드의 구간의 크기

* 구간의 가장 왼쪽 원소를 포함하는 높이가 h이상인 연속된 구간의 최대길이

* 구간의 가장 오른쪽 원소를 포함하는 높이가 h이상인 연속된 구간의 최대길이

* 구간에서 높이가 h이상인 연속한 구간의 최대길이

 

세그먼트 트리의 정의는 KOI 금광 문제와 유사하다.

 

위 세그먼트 트리를 사용하여 스토그램에서 연속하게 높이가 h보다 큰 직사각형이 w개 이상 존재하는지 판별할 수 있다. 그러나 문제는 세그먼트 트리를 $N$개 만들어야 하기 때문에 총 시간 복잡도가 $O(N^2)$이라는 것이다.

 

위 과정은 퍼시스턴트 세그먼트 트리(pst)로 최적화할 수 있다. 한 높이 $h$와 다음 높이 $h'$에 대해, $h$의 세그와 $h'$의 세그는 단 하나의 리프 노드만 다르다. 따라서 작은 높이부터 큰 높이 순서대로 보면서 세그먼트 트리가 어떻게 변화하는지를 저장해 주면 된다.