BOJ. Histogram (1725)

[Link] https://www.acmicpc.net/problem/1725

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
int seg[2 * N];
ll h[N];
int n;
ll ans = 0;

void init() {
  for(int i = 0; i < n; i++) seg[i + n] = i;
  for(int i = n - 1; i > 0; i--)
    seg[i] = h[seg[i<<1]] < h[seg[i<<1|1]] ? seg[i<<1] : seg[i<<1|1];
}

int query(int l, int r) {
  int min = 1e9, minIdx = 0;
  for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if(l & 1) {
      if(min > h[seg[l]]) {
        minIdx = seg[l];
        min = h[minIdx];
      }
      l++;
    }
    if(r & 1) {
      if(min > h[seg[--r]]) {
        minIdx = seg[r];
        min = h[minIdx];
      }
    }
  }
  return minIdx;
}

void bipartite(int l, int r) { //Does not include r
  if(l >= r) return;
  if(l + 1 == r) {
    ans = max(ans, h[l]);
    return;
  }
  int minIdx = query(l, r);
  ans = max(ans, h[minIdx] * (r - l));
  bipartite(l, minIdx);
  bipartite(minIdx + 1, r);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> h[i];
  init();
  bipartite(0, n);
  cout << ans;
}