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

앞에서 본 히스토그램과 같은 문제이다.

이전에는 스택으로 풀었으니 이번에는 세그먼트 트리로 풀어볼 것이다.

구현은 좀 더 복잡하지만 개인적으로 직관적인 이해는 세그트리 방식이 더 쉬웠던거 같다.

간단하게 그냥 구간에서 높이가 최소인 곳을 찾고 그 점을 기준으로 왼쪽, 오른쪽에서 넓이가 최대인 직사각형과을 비교하면 된다.

구간의 왼쪽에서의 최대넓이, 구간의 오른쪽에서의 최대넓이, 기준점의 높이*구간의 길이 이렇게 3개의 값을 비교해서 최대를 찾으면 끝난다.

#include<stdio.h>
#include<algorithm>
using namespace std;
long long arr[100004];
int N;
long long big = 1000000005;
struct Data{
    long long ind,val;
    bool operator<(const Data R)const{
        return val<R.val;
    }
}seg[300004];
Data init(int n, int s, int e)
{
    if(s==e) return seg[n] = {s,arr[s]};
    int m = (s+e)/2;
    return seg[n]=min(init(n*2,s,m),init(n*2+1,m+1,e));
}
Data finds(int n, int s, int e, int fs, int fe)
{
    if(e<fs || s>fe) return {0,big};
    if(fs<=s && e<=fe) return seg[n];
    int m = (s+e)/2;
    return min(finds(n*2,s,m,fs,fe),finds(n*2+1,m+1,e,fs,fe));
}
long long solve(int s, int e)
{
    if(s>e) return 0;
    int minv = finds(1,1,N,s,e).ind;
    long long maxv = max(solve(s,minv-1),solve(minv+1,e));
    return max(maxv,arr[minv]*(e-s+1));
}
int main()
{
    while(true){
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
        {
            scanf("%lld",&arr[i]);
        }
        if(N==0) break;
        init(1,1,N);
        long long ans = solve(1,N);
        printf("%lld\n",ans);
    }
}

init과 finds는 최소 세그트리 구현이고, solve는 세그트리를 이용한 분할정복 함수이다.