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

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

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

 

 

티어 : 플래5

 

세그먼트 트리로 풀었다.

다른 방법으로도 풀어봐야겠다.

 

#include<stdio.h>
#include<algorithm>

using namespace std;
int n, arr[100005], seg[400005];

int init(int index, int left, int right){
    if(left == right) return seg[index] = arr[left];
    int mid = (left + right) / 2;
    return seg[index] = min(init(index*2, left, mid), init(index*2+1, mid+1, right));
}

int findLeft(int index, int left, int right, int s, int e, int value){
    if(left > e || s > right) return 0;
    if(seg[index] >= value) return 0;
    if(left == right){
        if(s <= left && right <= e) return left;
        else return 0;
    }
    int mid = (left + right) / 2;
    if(s <= left && right <= e && seg[index*2+1] < value) return findLeft(index*2+1, mid+1, right, s, e, value);
    return max(findLeft(index*2+1, mid+1, right, s, e, value), findLeft(index*2, left, mid, s, e, value));
}

int findRight(int index, int left, int right, int s, int e, int value){
    if(left > e || s > right) return n+1;
    if(seg[index] >= value) return n+1;
    if(left == right){
        if(s <= left && right <= e) return left;
        else return n+1;
    }
    int mid = (left + right) / 2;
    if(s <= left && right <= e && seg[index*2] < value) return findRight(index*2, left, mid, s, e, value);
    return min(findRight(index*2+1, mid+1, right, s, e, value), findRight(index*2, left, mid, s, e, value));
}

int main()
{
    while(1){
        scanf("%d", &n);
        if(n == 0) return 0;
        for(int i=1 ; i<=n ; i++) scanf("%d", &arr[i]);
        init(1, 1, n);
        
        long long int max = 0, a, b;
        for(int i=1 ; i<=n ; i++){
            a = findLeft(1, 1, n, 1, i, arr[i]);
            b = findRight(1, 1, n, i, n, arr[i]);
            if(max < (b-a-1)*arr[i]) max = (b-a-1)*arr[i];
        }
        printf("%lld\n", max);
    }
}