AIOJ

Introduction

A Cartesian tree is a binary tree in which each node consists of a key-value pair $(k,w)$ . The keys $k$ satisfy the binary search tree (BST) property, while $w$ satisfies the heap property. If the $k,w$ values of a Cartesian tree are fixed, and the $k$ values are all distinct and the $w$ values are also all distinct, then the structure of the Cartesian tree is unique. The following figure illustrates this:

(Figure from Wikipedia)

The Cartesian tree above can be viewed as taking the array element values as the keys $w$ and the array indices as the keys $k$ . We can see that the keys $k$ satisfy the BST property, while the keys $w$ satisfy the min-heap property. Moreover, from the binary search tree property, we can see that this special Cartesian tree has a contiguous interval of indices in every subtree.

In contests, when using a Cartesian tree, the array index is commonly used as the key $k$ , so the array index $k$ satisfies the BST property.

Below, whenever $k,w$ are used without further qualification, $k$ is assumed to satisfy the BST property and $w$ is assumed to satisfy the heap property.

Building a Cartesian Tree with a Monotonic Stack

Procedure

Consider inserting the elements into the current Cartesian tree one by one in ascending order of $k$ .

For a Cartesian tree, define the right spine as the chain formed by starting at the root and repeatedly following the right child until reaching a leaf. After a node is inserted, it must lie on the right spine. Since the nodes are inserted in ascending order of $k$ satisfying the BST property, the newly inserted node must be at the far right of the tree. This node cannot be a left child and has no right child.

We therefore perform the following process: compare the nodes on the right spine with the current node $u$ 's $w$ from bottom to top. If we find a node $x$ on the right spine such that $w_x<w_u$ , attach $u$ as the right child of $x$ , and make the right subtree originally belonging to $x$ the left subtree of $u$ .

The part enclosed by the red box in the figure is the right spine that we maintain:

build

Clearly, each value enters and leaves the right spine at most once (equivalently, each node remains on the right spine for one contiguous period of time). This process can be maintained with a monotonic stack, with the stack storing the nodes on the right spine of the current Cartesian tree. When a node is no longer on the right spine, pop it from the stack. Thus each node enters and leaves the stack at most once, giving a complexity of $O(n)$ .

Cartesian Trees and Treaps

In fact, a Treap is a type of Cartesian tree; the only difference is that the values of $w$ in a Treap are completely random. Treaps have a linear-time construction algorithm. If the keys $k$ are sorted in advance, the monotonic-stack algorithm above can be used to construct one, although it is rarely used this way.

C++ Implementation

// stk stores the indices of Cartesian-tree nodes in the sequence
for (int i = 1; i <= n; i++) {
  int k = top;  // top denotes the stack top before this operation; k denotes the current stack top
  while (k > 0 && w[stk[k]] > w[i]) k--;  // Maintain the nodes on the right spine
  if (k) rs[stk[k]] = i;  // right child of the stack-top element := current element
  if (k < top) ls[i] = stk[k + 1];  // left child of current element := the last element popped
  stk[++k] = i;                     // Push the current element
  top = k;
}

Examples

HDU 1506. Largest Rectangle in a Histogram

There are $n$ positions, and the height at each position is $h_i$ . Find the maximum subrectangle. The following figure illustrates this:

The shaded part is the maximum subrectangle in the figure.

Solution

Specifically, we use the index as the key $k$ and $h_i$ as the key $w$ , and construct a Cartesian tree satisfying the min-heap property for the pairs $(i,h_i)$ .

We then enumerate every node $u$ and take $w_u$ (that is, the height of node $u$ , namely $h$ ) as the height of the maximum subrectangle. Since the Cartesian tree we constructed satisfies the min-heap property, the heights of all nodes in the subtree of $u$ are greater than or equal to the height of $u$ . We also know that the indices in the subtree of $u$ form a contiguous interval. Therefore, we only need to know the size of the subtree, after which we can calculate the area of the maximum subrectangle over this interval. Update the answer with the value calculated for each node. Clearly, this can be completed with a single DFS, so the complexity is $O(n)$ .

Reference Implementation

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int N = 100000 + 10, INF = 0x3f3f3f3f;

struct node {
  int idx, val, par, ch[2];

  friend bool operator<(node a, node b) { return a.idx < b.idx; }

  void init(int _idx, int _val, int _par) {
    idx = _idx, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
} tree[N];

int root, top, stk[N];
ll ans;

int cartesian_build(int n) {  // Build the tree with the min-heap property
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}

int dfs(int x) {  // A single DFS is enough to update the answer
  if (!x) return 0;
  int sz = dfs(tree[x].ch[0]);
  sz += dfs(tree[x].ch[1]);
  ans = max(ans, (ll)(sz + 1) * tree[x].val);
  return sz + 1;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, hi;
  while (cin >> n, n) {
    tree[0].init(0, 0, 0);
    for (int i = 1; i <= n; i++) {
      cin >> hi;
      tree[i].init(i, hi, 0);
    }
    root = cartesian_build(n);
    ans = 0;
    dfs(root);
    cout << ans << '\n';
  }
  return 0;
}

References

Cartesian tree - Wikipedia