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

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

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

<문제>

세그먼트 트리를 이용했다.

리프노드에는 각 직사각형의 높이를 저장하고, 리프노드가 아니라면 구간중 가장 작은 높이를 저장한다.

end-start+1이 느리게 갱신되는 세그먼트 트리랑 겹치는 부분이 있지만 이 문제는 lazy propagation은 아니고,

구간중 가장 짧은 높이는 세그먼트 트리로, end-start+1으로 가로길이를 구해 직사각형의 넓이를 계산하는 것 뿐이다.

<소스코드>

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
int num[100001];
vector <int>segTree;
void makeSegTree(int node, int start, int end) {
    if (start == end) {
        segTree[node] = start;
        return;
    }
    int mid = (start + end) / 2;
    makeSegTree(node * 2, start, mid);
    makeSegTree(node * 2 + 1, mid + 1, end);
    if (num[segTree[node * 2]] <= num[segTree[node * 2 + 1]]) {
        segTree[node] = segTree[node * 2];
    }
    else {
        segTree[node] = segTree[node * 2 + 1];
    }
}
int findIdx(int node, int start, int end, int left, int right) {
    if (left > end || right < start) return -1;
    if (left <= start && end <= right)return segTree[node];
 
    int mid = (start + end) / 2;
    int leftRes = findIdx(node * 2, start, mid, left, right);
    int rightRes = findIdx(node * 2 + 1, mid + 1, end, left, right);
    if (leftRes == -1)
        return rightRes;
    if (rightRes == -1)
        return leftRes;
    if (num[leftRes] <= num[rightRes])
        return leftRes;
    else
        return rightRes;
}
ll solve(int start, int end) {
    int numSize = n;
    int m = findIdx(1, 0, numSize-1, start, end);
    ll area = (ll)(end - start + 1) * (ll)num[m];
 
    if (start <= m - 1) {
        ll tmp = solve(start, m - 1);
        area = max(tmp, area);
    }
    if (m + 1 <= end) {
        ll tmp = solve(m + 1, end);
        area = max(tmp, area);
    }
    return area;
}
int main(void) {
    while (1) {
        scanf("%d", &n);
        if (n == 0)break;
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);
 
        int treeHeight = (int)ceil(log2(n));
        int treeSize = (1 << (treeHeight + 1));
        segTree.resize(treeSize);
        makeSegTree(1, 0, n - 1);
 
        printf("%lld\n", solve(0, n - 1));
        segTree.clear();
    }
    return 0;
}