Cartesian Tree
(Graph/Tree/cartesian_tree.py)

• View this file on GitHub
• Last update: 2021-02-03 22:14:24+09:00

概要

Cartesian Tree を求めるアルゴリズム。

使い方

cartesian_tree(arr: Sequence[int]) -> List[int]
dinstinct な数列 arr から誘導される Cartesian Tree を求め、各頂点の親の配列を返す。計算量 $O(V)$

参考

• 列を最小値で分割して再帰するパターンと Cartesian tree - うさぎ小屋

Verified with

• TestCase/LibraryChecker/cartesian_tree.test.py

Code

def cartesian_tree(arr):
    n = len(arr)
    par = [-1] * n
    stack = []
    for i in range(n):
        prv_i = -1
        while stack and arr[i] < arr[stack[-1]]:
            prv_i = stack.pop()
        if prv_i != -1:
            par[prv_i] = i
        if stack:
            par[i] = stack[-1]
        stack.append(i)
    return par

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page