AIOJ

Introduction

The hanging-line method applies to a subset of the problems solvable with a monotonic stack. More specifically, it can be used when:

monotonic information must be maintained while scanning a sequence;
a monotonic stack can solve the problem;
no binary search on the monotonic stack is needed.

The hanging-line method may appear replaceable and not very useful, but its concept is simpler than that of a monotonic stack, making it more suitable for beginners in OI to understand and use for problems such as maximum submatrices.

Examples

SPOJ HISTOGRA - Largest Rectangle in a Histogram

In a row there are $n$ rectangles of width $1$ . Find the maximum-area subrectangle contained in these rectangles.

A hanging line is a vertical line with an initial position and a height. It may move left or right as long as its upper endpoint does not exceed the height of the rectangle at its current position.

For a hanging line, move it left and right as far as possible without letting its upper endpoint exceed the current rectangle height or crossing the boundary. The area swept by the line is then the largest rectangle containing that line. It is easy to see that a maximum subrectangle must contain a hanging line initially located at $i$ with height $h_i$ . Enumerating this process takes $O(n ^ 2)$ time, but the hanging-line method reduces it to $O(n)$ .

Consider how to find the leftmost position a hanging line can reach efficiently.

Process

Let $l_i$ be the leftmost position reachable by the hanging line currently at position $i$ . Initially, $l_i$ is $i$ ; we then determine whether it can extend farther left.

If $l_i = 1$ , the boundary has been reached and it cannot extend farther.
If $a_i > a_{l_i - 1}$ , the line cannot extend farther left from its current position.
If $a_i \le a_{l_i - 1}$ , it can extend farther left. Moreover, any position reachable by the hanging line at $l_i - 1$ is also reachable by the line at $i$ , so update $l_i$ to $l_{l_i - 1}$ and continue checking.

An amortized analysis shows that each $l_i$ is traversed by other $l_j$ at most once, so the time complexity is $O(n)$ .

Implementation

Reference code

#include <algorithm>
#include <iostream>
using std::max;
constexpr int N = 100010;
int n, a[N];
int l[N], r[N];
long long ans;
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n, n) {
    ans = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], l[i] = r[i] = i;
    for (int i = 1; i <= n; i++)
      while (l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1];
    for (int i = n; i >= 1; i--)
      while (r[i] < n && a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1];
    for (int i = 1; i <= n; i++)
      ans = max(ans, (long long)(r[i] - l[i] + 1) * a[i]);
    cout << ans << '\n';
  }
  return 0;
}

UVa1619 Feel Good

Given a sequence of length $n$ , find a subinterval maximizing the product of its minimum value and the sum of its elements. Among intervals with the maximum value, minimize the length; among those, minimize the left endpoint.

Here we can enumerate the minimum. Treat the value $a_i$ at each position as the minimum and extend from $i$ in both directions to find the widest interval $\min\limits _ {j = l} ^ r a_j = a_i$ satisfying $[l, r]$ . This turns the problem into the hanging-line model.

Reference code

#include <cstring>
#include <iostream>
constexpr int N = 100010;
int n, a[N], l[N], r[N];
long long sum[N];
long long ans;
int ansl, ansr;
bool fir = true;
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (cin >> n) {
    memset(a, -1, sizeof(a));
    if (!fir)
      cout << '\n';
    else
      fir = false;
    ans = 0;
    ansl = ansr = 1;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      sum[i] = sum[i - 1] + a[i];
      l[i] = r[i] = i;
    }
    for (int i = 1; i <= n; i++)
      while (a[l[i] - 1] >= a[i]) l[i] = l[l[i] - 1];
    for (int i = n; i >= 1; i--)
      while (a[r[i] + 1] >= a[i]) r[i] = r[r[i] + 1];
    for (int i = 1; i <= n; i++) {
      long long x = a[i] * (sum[r[i]] - sum[l[i] - 1]);
      if (ans < x || (ans == x && ansr - ansl > r[i] - l[i]))
        ans = x, ansl = l[i], ansr = r[i];
    }
    cout << ans << '\n' << ansl << ' ' << ansr << '\n';
  }
  return 0;
}

Maximum subrectangle

P4147 Jade Toad Palace

Given an $n \times m$ matrix containing 'F' and 'R', find the area of the largest submatrix whose every entry is 'F', multiplied by $\times 3$ .

The model of this problem is similar to that of the first example. If, for each row, we consider all positions and use the distance that the value at $(x, y)$ can extend upward as the height of its hanging line, then the maximum submatrix must be one of the largest rectangles obtained by extending these hanging lines left and right.

Reference code

#include <algorithm>
#include <iostream>
int m, n, a[1010], l[1010], r[1010], ans;
using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      l[j] = r[j] = j;
    }
    char s[3];
    for (int j = 1; j <= m; j++) {
      cin >> s;
      if (s[0] == 'F')
        a[j]++;
      else if (s[0] == 'R')
        a[j] = 0;
    }
    for (int j = 1; j <= m; j++)
      while (l[j] != 1 && a[l[j] - 1] >= a[j]) l[j] = l[l[j] - 1];
    for (int j = m; j >= 1; j--)
      while (r[j] != m && a[r[j] + 1] >= a[j]) r[j] = r[r[j] + 1];
    for (int j = 1; j <= m; j++) ans = std::max(ans, (r[j] - l[j] + 1) * a[j]);
  }
  cout << ans * 3;
  return 0;
}

Exercises

P1169 ZJOI2007 Board Construction