[BOJ 6549] 히스토그램에서 가장 큰 직사각형

문제 출처 : https://www.acmicpc.net/problem/6549

 

풀이 :

 

스택 or 분할정복 + 세그먼트 트리 로 풀 수 있는 문제입니다.

저는 분할정복 + 세그먼트 트리로 풀었고

세그먼트 트리로 구간의 최솟값의 인덱스를 저장하여

최솟값 왼쪽 구간과 최솟값 오른쪽 구간으로 나누어서 분할 정복을 시행하였습니다.

 

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
 
int n, base, hei[100001], seg[1 << 18];
 
int search(int idx, int l, int r, int a, int b) {
    if (l > b || r < a)return -1;
    if (a <= l && b >= r)return seg[idx];
    int mid = (l + r + 1) / 2;
    int rl = search(idx * 2, l, mid - 1, a, b), rr = search(idx * 2 + 1, mid, r, a, b);
    if (rl == -1)return rr;
    if (rr == -1)return rl;
    if (hei[rl] > hei[rr])return rr;
    return rl;
}
 
ll solve(int s,int e) {
    if (s > e)return -1;
    int minIdx = search(1, 0, base, s, e);
    ll ret = max(solve(s, minIdx - 1), solve(minIdx + 1, e));
    ret = max(ret, (ll)hei[minIdx] * (e - s + 1));
    return ret;
}
 
int main()
{
    hei[100000] = 1e9;
    while (1) {
        cin >> n;
        if (!n)break;
        base = pow(2, (int)log2(n) + 1);
        for (int i = 0; i < n; i++) {
            cin >> hei[i];
            seg[i + base] = i;
        }
        for (int i = base + n; i < base * 2; i++)seg[i] = 100000;
        for (int i = base - 1; i; i--) {
            if (hei[seg[i * 2 + 1]] < hei[seg[i * 2]])seg[i] = seg[i * 2 + 1];
            else seg[i] = seg[i * 2];
        }
        cout << solve(0, n - 1) << '\n';
    }
}