cartesian_tree

ソースコード

from titan_pylib.graph.cartesian_tree import cartesian_tree

view on github

展開済みコード

 1# from titan_pylib.graph.cartesian_tree import cartesian_tree
 2def cartesian_tree(a: list[int]) -> tuple[list[int], list[int], list[int]]:
 3    """Get cartesian_tree. / O(N)"""
 4    n = len(a)
 5    par = [-1] * n
 6    left = [-1] * n
 7    right = [-1] * n
 8    path = []
 9    for i, e in enumerate(a):
10        pre = -1
11        while path and e < a[path[-1]]:
12            pre = path.pop()
13        if pre != -1:
14            par[pre] = i
15        if path:
16            par[i] = path[-1]
17        path.append(i)
18    for i, p in enumerate(par):
19        if p == -1:
20            continue
21        if i < p:
22            left[p] = i
23        else:
24            right[p] = i
25    return par, left, right

仕様

cartesian_tree(a: list[int]) → tuple[list[int], list[int], list[int]][source]

Get cartesian_tree. / O(N)