Cartesian Tree

列 $a$ の最小値の位置を根とし、それより左の部分と右の部分から同じように作った木を、それぞれ左の部分木・右の部分木とする二分木です。どの頂点の部分木も元の列の連続する区間になり、その区間の最小値が部分木の根にあります。通りがけ順に並べると元の列の順番になります。

左から順に、根から右の子だけをたどった道をスタックに持っておき、 $a_i$ より大きい頂点を道から取り除いて $i$ の左の部分木にし、 $i$ を道の最後につなぎます。各頂点はスタックに 1 回入って 1 回出るだけなので $O(N)$ です。再帰は使いません。

同じ値があるときは、左にあるものが祖先になります(同じ値だけが並んでいると、右の子をたどる 1 本の道になります)。根は最小値のうち最も左にあるものです。

根でない頂点 $v$ は、v < par[v] なら par[v] の左の子、v > par[v] なら右の子です。最大値を根にするときは、値を $-1$ 倍して cartesian_tree([-x for x in a]) とします(このときも、同じ値では左にあるものが祖先になります)。

$l \le r$ のとき、 $a_l, \ldots, a_r$ の最小値(のうち最も左のもの)の位置は、 $l$ と $r$ の LCA です。

頂点 $v$ の部分木が受け持つ区間を $[L_v, R_v)$ とすると、 $L_v \le x \le v < y \le R_v$ となる区間 $[x, y)$ は、ちょうど $a_v$ を最小値(のうち最も左のもの)とする区間です。たとえば、すべての区間の最小値の和は $a_v (v - L_v + 1)(R_v - v)$ の和で、ヒストグラムの中の最大の長方形の面積は $a_v (R_v - L_v)$ の最大値です。

例( $L_v$ は左の子から、 $R_v$ は右の子から求まるので、 $L_v$ は左から、 $R_v$ は右から順に求める):

a = [2, 1, 5, 6, 2, 3]
n = len(a)
par = cartesian_tree(a)
print(par)  # [1, -1, 4, 2, 1, 4]
L = list(range(n))  # 頂点 v の部分木は区間 [L[v], R[v])
R = list(range(1, n + 1))
for v in range(n):
    if v < par[v]:  # v は par[v] の左の子
        L[par[v]] = L[v]
for v in range(n - 1, -1, -1):
    if 0 <= par[v] < v:  # v は par[v] の右の子
        R[par[v]] = R[v]
print(sum(a[v] * (v - L[v] + 1) * (R[v] - v) for v in range(n)))  # 43
print(max(a[v] * (R[v] - L[v]) for v in range(n)))  # 10

コード

def cartesian_tree(a):
    # a の最小値を根とする Cartesian Tree の親のリスト par(根は par[root] = -1)
    # 同じ値どうしでは左にあるものが祖先になる
    n = len(a)
    par = [-1] * n
    st = []  # 根から右の子だけをたどった道の頂点
    for i in range(n):
        x = a[i]
        last = -1
        while st and a[st[-1]] > x:
            last = st.pop()
        if last != -1:
            par[last] = i  # 取り除いた部分は i の左の部分木になる
        if st:
            par[i] = st[-1]  # i は残った道の最後の頂点の右の子になる
        st.append(i)
    return par