히스토그램에서 가장 큰 직사각형 리턴즈

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

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

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

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