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

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

기본적으로 분할 정복의 아이디어를 사용하며, segment tree를 보조 도구로 사용해주면 된다.

[lo, hi] 구간의 막대들에 대해서 막대[m] (lo <= m <= hi)이 가장 낮은 높이를 가졌다고 해보자.

이 때, [lo, hi] 구간의 최대 직사각형은 아래 3가지 경우 중 하나가 될 것이다.

• Case 1: 막대[m]을 포함한다.

• Case 2: 막대[m]의 왼쪽 막대들로만 구성된다.

• Case 3: 막대[m]의 오른쪽 막대들로만 구성된다.

Case 2/3이야 자명하게 재귀로 호출해주면 되는 경우이고, Case 1의 경우 막대[m]이 [lo,hi]내 가장 낮은 막대이므로 곧 그 넓이가 (hi-lo+1)*막대[m]이 된다.

상술한 것이 곧 분할정복 아이디어의 전부이고, [lo,hi]내 가장 낮은 막대의 위치 m을 찾는 쿼리를 segment tree를 통해 만들어주면 된다.

#include <iostream>
#include <vector>
#include <limits>
#include <cstdint>

using namespace std;

static const size_t kMaxN = 100000;

class SegmentTree
{
public:
  size_t n;
  size_t bars[kMaxN + 1];
  size_t node[4 * kMaxN];

public:
  SegmentTree(void) : n(0)
  {
    bars[0] = numeric_limits<size_t>::max();
  }

  size_t Initialize(const size_t root, const size_t left, const size_t right)
  {
    if (left == right)
    {
      node[root] = left;
      return node[root];
    }

    size_t mid = (left + right) / 2;
    size_t left_index = Initialize(2 * root, left, mid);
    size_t right_index = Initialize(2 * root + 1, mid + 1, right);

    node[root] = (bars[left_index] < bars[right_index]) ? left_index : right_index;

    return node[root];
  }

  size_t Query(const size_t root, const size_t left, const size_t right, const size_t query_left,
               const size_t query_right)
  {
    if (query_right < left || right < query_left)
    {
      return 0;
    }

    if (query_left <= left && right <= query_right)
    {
      return node[root];
    }

    size_t mid = (left + right) / 2;
    size_t left_index = Query(2 * root, left, mid, query_left, query_right);
    size_t right_index = Query(2 * root + 1, mid + 1, right, query_left, query_right);

    return (bars[left_index] < bars[right_index]) ? left_index : right_index;
  }
};

SegmentTree segment_tree;

int64_t Solve(SegmentTree& segment_tree, const size_t lo, const size_t hi)
{
  if (lo > hi)
  {
    return static_cast<int64_t>(0);
  }

  if (lo == hi)
  {
    return static_cast<int64_t>(segment_tree.bars[lo]);
  }

  size_t mid = segment_tree.Query(1, 1, segment_tree.n, lo, hi);

  int64_t ret = (hi - lo + 1) * segment_tree.bars[mid];

  ret = max(ret, Solve(segment_tree, lo, mid - 1));
  ret = max(ret, Solve(segment_tree, mid + 1, hi));

  return ret;
}

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  while (true)
  {
    cin >> segment_tree.n;
    if (segment_tree.n == 0)
    {
      break;
    }

    for (size_t idx = 1; idx <= segment_tree.n; ++idx)
    {
      cin >> segment_tree.bars[idx];
    }

    segment_tree.Initialize(1, 1, segment_tree.n);

    cout << Solve(segment_tree, 1, segment_tree.n) << "\n";
  }

  return 0;
}