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

시작하면서

　이번 문제는 세그먼트 트리(Segment Tree) 문제이다.

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

​

문제 이해

​ 이번 문제는 잘 설명되어 있는 링크로 대체한다.

LINK

​

해결

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

void InitSegmentTree(vector<int>& tree, vector<int>& ary, int node, int start, int end)
{
    if (start == end)
    {
        tree[node] = start;
        return;
    }

    int mid = (start + end) * 0.5f;

    InitSegmentTree(tree, ary, node * 2, start, mid);
    InitSegmentTree(tree, ary, node * 2 + 1, mid + 1, end);

    if (ary[tree[node * 2]] <= ary[tree[node * 2 + 1]])
    {
        tree[node] = tree[node * 2];
    }
    else
    {
        tree[node] = tree[node * 2 + 1];
    }
}

int QuerySegmentTree(vector<int>& tree, vector<int>& ary, int node, int start, int end, int left, int right)
{
    if (left > end || right < start)
        return -1;

    if (left <= start && end <= right)
        return tree[node];

    int mid = (start + end) * 0.5f;
    int l = QuerySegmentTree(tree, ary, node * 2, start, mid, left, right);
    int r = QuerySegmentTree(tree, ary, node * 2 + 1, mid + 1, end, left, right);

    if (l == -1)
    {
        return r;
    }
    else if (r == -1)
    {
        return l;
    }
    else if (ary[l] <= ary[r])
    {
        return l;
    }
    else
    {
        return r;
    }
}

long long GetLargestRectangle(vector<int>& tree, vector<int>& ary, int start, int end)
{
    int size = ary.size() - 1;
    int query = QuerySegmentTree(tree, ary, 1, 0, size, start, end);
    long long result = ((long long)end - start + 1) * ary[query];

    if (start <= query - 1)
    {
        long long cmp = GetLargestRectangle(tree, ary, start, query - 1);
        result = max(result, cmp);
    }

    if (query + 1 <= end)
    {
        long long cmp = GetLargestRectangle(tree, ary, query + 1, end);
        result = max(result, cmp);
    }

    return result;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    int n;
    vector<int> heights;
    vector<int> tree;

    while (true)
    {
        cin >> n;

        if (n == 0)
            break;

        int height = (int)(ceil(log2(n)) + 1e-9);
        heights.resize(n);
        tree.resize(1 << (height + 1));

        for (int i = 0; i < n; i++)
        {
            cin >> heights[i];
        }

        InitSegmentTree(tree, heights, 1, 0, n - 1);

        cout << GetLargestRectangle(tree, heights, 0, n - 1) << "\n";
    }

    return 0;
}