Source code for titan_pylib.graph.cartesian_tree


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