[세그먼트 트리/파이썬] 백준 6549번: 히스토그램에서 가장 큰 직사각형 / 플래5

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

6549번: 히스토그램에서 가장 큰 직사각형

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def merge(left, right):
    if left[0] < right[0]:
        return left
    else:
        return right

def build(node, left, right):
    if left == right:  # leaf node
        s_tree[node] = [nums[left], left]
        return s_tree[node]

    mid = left + (right - left)//2
    a = build(2*node, left, mid)
    b = build(2*node+1, mid+1, right)
    s_tree[node] = merge(a, b)
    return s_tree[node]

def query(start, end, node, left, right):
    if end < left or right < start:
        return [9876543210, -1]

    if start <= left and right <= end:
        return s_tree[node]

    mid = left + (right - left)//2
    a = query(start, end, 2*node, left, mid)
    b = query(start, end, 2*node+1, mid+1, right)
    return merge(a, b)

def divide_and_conquer(lo, hi):
    if lo == hi:
        return nums[lo]
    if lo > hi:
        return -1

    minimum, idx = query(lo, hi, 1, 0, n-1)
    a = divide_and_conquer(lo, idx-1)
    b = divide_and_conquer(idx + 1, hi)
    c = minimum * (hi - lo + 1)
    return max(a, b, c)


while True:
    nums = list(map(int, input().split()))
    n = nums.pop(0)
    if n == 0:
        quit()

    s_tree = [[0 for _ in range(2)] for _ in range(4 * n)]
    build(1, 0, n-1)
    print(divide_and_conquer(0, n-1))

분할 정복이 핵심인데, 단순히 구간을 절반씩 나누면 안된다. 최소 높이를 찾아서 그 지점을 기준으로 양 쪽을 분할해야 한다. 해당 구간에서 최대 넓이는 이 지점을 기준으로 왼쪽에 있거나, 오른쪽에 있거나, 걸쳐있기 때문이다.

걸쳐있는 경우에는 이 지점이 어차피 최소 높이기 때문에 구간 길이* 높이 해주면 된다.

이때 최소 높이를 빠르게 찾기 위해 세그먼트 트리를 사용한다.