CartesianTree
(expansion/tree/CartesianTree.py)

• View this file on GitHub
• Last update: 2023-07-05 23:59:21+09:00

概要

与えられた数列からCartesianTreeを求めます． 返り値は親の index 値を持つ形式（自分自身が親の場合，自分自身の index）

使い方

par = CartesianTree(A)

Code

def CartesianTree(A):
    n = len(A)
    P = [-1] * n
    B = [-1] * n
    p = -1

    for i, a in enumerate(A):
        while p >= 0 and a < A[B[p]]:
            j = B[p]
            p -= 1
            if p >= 0 and a < A[B[p]]:
                P[j] = B[p]
            else:
                P[j] = i

        p += 1
        B[p] = i

    for i in range(p, 0, -1):
        P[B[i]] = B[i - 1]

    i = B[0]
    P[i] = i
    return P

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page