Largest Rectangle in a Histogram Returns

너비 $w$인 한 구간의 모든 막대 높이를 $h$ 이상으로 만들 수 있는지 생각하자. 이 구간에는 $B$에서 가장 큰 $w$개만 쓰면 충분하다. 구간의 $A$를 오름차순, 선택한 $B$를 내림차순으로 짝지었을 때 모든 합이 $h$ 이상이면 가능하고, 그렇지 않으면 어떤 짝짓기도 불가능하다.

각 $A_i$에 대해 $A_i+B_j \geq h$를 만족하는 의 개수를 라 하자. 길이 인 구간의 들을 오름차순으로 정렬한 값을 라 하면 가능할 필요충분조건은 모든 에 대해 인 것이다.

슬라이딩 윈도우에서 $r_i$의 빈도를 관리한다. $D_k=\#\{i:r_i\leq k\}-k$라 두면 조건은 모든 이다. 값 의 최대 접두사 합을 저장하는 세그먼트 트리를 사용하면 원소 추가와 삭제, 조건 확인을 각각 에 할 수 있다.

각 너비 $w$에 대해 가능한 최대 높이 $h$를 이분 탐색하고 $wh$의 최댓값을 취한다. 시간 복잡도는 $O(N^2\log N\log V)$이다.