[C++] 히스토그램에서 가장 큰 직사각형 (백준 6549번)

https://www.acmicpc.net/problem/6549
 
히스토그램에서 가장 넓이가 큰 직사각형은 다음의 셋 중 하나이다.
1. 최솟값을 포함하면서 전체 구간의 직사각형
2. 최솟값 기준 왼쪽 구간에서의 가장 큰 직사각형
3. 최솟값 기준 오른쪽 구간에서의 가장 큰 직사각형

그 이유는 다음과 같다.
최대 직사각형은 최댓값을 포함할 수도 있고 포함하지 않을 수도 있다. 
만약 최솟값을 포함한다면 구간을 최대로 잡아도 좌우로는 잘리지 않기 때문에, 양쪽 끝까지 구간을 잡는 것이 최대이다.
만약 최솟값을 포함하지 않는다면 해당 최솟값을 기준으로 구간이 이미 잘렸다고 생각하면 된다. 그렇기 때문에 그 값 기준 왼쪽에서의 최대와 오른쪽에서의 최대를 구한다.
 
따라서 세그먼트 트리로 저장해야 하는 정보는 구간 별 최소값의 인덱스이다. 
세그먼트 트리를 초기화하고, 그걸 활용해서 분할 정복을 하면 문제를 해결할 수 있다.
 

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> arr;
vector<int> tree;

int init(int idx, int l, int r) {
    if (l == r) return tree[idx] = l;
    int m = (l + r) / 2;

    int lidx = init(idx * 2, l, m);
    int ridx = init(idx * 2 + 1, m + 1, r);

    if (arr[lidx] < arr[ridx]) return tree[idx] = lidx;
    else return tree[idx] = ridx;
}

int query(int idx, int l, int r, int wl, int wr) {
    if (wr < l || wl > r) return -1;
    if (wl <= l && wr >= r) return tree[idx];

    int m = (l + r) / 2;
    int lidx = query(idx * 2, l, m, wl, wr);
    int ridx = query(idx * 2 + 1, m + 1, r, wl, wr);

    if (lidx == -1) return ridx;
    if (ridx == -1) return lidx;

    if (arr[lidx] < arr[ridx]) return lidx;
    else return ridx;
}

int query(int wl, int wr) {
    return query(1, 1, n, wl, wr);
}

long long getMaxArea(int l, int r) {
    if (l > r) return 0;
    int minidx = query(l, r);
    long long maxArea = (long long) arr[minidx] * (r - l + 1);
    return max(maxArea, max(getMaxArea(l, minidx - 1), getMaxArea(minidx + 1, r)));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while (1) {
        cin >> n;
        if (n == 0) break;

        tree.assign(4 * n + 1, 0);
        arr.resize(n + 1);

        for (int i = 1; i < n + 1; i++) cin >> arr[i];

        init(1, 1, n);
    
        cout << getMaxArea(1, n) << '\n';
    }
}

(AC)