提出 #62587787

---

ソースコード 拡げる

from random import randint
from typing import Tuple


class Node:
    def __init__(self, key):
        self.key = key
        self.rnd = randint(0, 1 << 30)
        self.lch = None
        self.rch = None
        self.size = 1


class Treap:
    def __init__(self):
        self.root = None

    def size(self, node):
        return node.size if node else 0

    def pull(self, node):
        node.size = 1 + self.size(node.lch) + self.size(node.rch)

    def split_by_size(
        self, u: Node | None, size: int
    ) -> Tuple[Node | None, Node | None]:
        if u is None:
            return None, None
        if size <= self.size(u.lch):
            a, b = self.split_by_size(u.lch, size)
            u.lch = b
            self.pull(u)
            return a, u
        else:
            a, b = self.split_by_size(u.rch, size - self.size(u.lch) - 1)
            u.rch = a
            self.pull(u)
            return u, b

    def merge(self, a: Node | None, b: Node | None) -> Node | None:
        if a is None:
            return b
        if b is None:
            return a
        if a.rnd > b.rnd:
            a.rch = self.merge(a.rch, b)
            self.pull(a)
            return a
        else:
            b.lch = self.merge(a, b.lch)
            self.pull(b)
            return b

    def insert_at_pos(self, k, p: int):
        t1, t2 = self.split_by_size(self.root, p)
        self.root = self.merge(t1, Node(k))
        self.root = self.merge(self.root, t2)

    def traverse(self, u: Node | None, f, dep: int = 0, mode="in"):
        if u is None:
            f(u, dep)
        else:
            if mode == "pre":
                f(u, dep)
                self.traverse(u.lch, f, dep + 1, mode)
                self.traverse(u.rch, f, dep + 1, mode)
            elif mode == "in":
                self.traverse(u.lch, f, dep + 1, mode)
                f(u, dep)
                self.traverse(u.rch, f, dep + 1, mode)
            else:  # post
                self.traverse(u.lch, f, dep + 1, mode)
                self.traverse(u.rch, f, dep + 1, mode)
                f(u, dep)

    def to_list(self):
        arr = []

        def f(node, dep):
            if node:
                arr.append(node.key)

        self.traverse(self.root, f, mode="in")
        return arr

    def show(self):
        def f(node, dep):
            if node is None:
                print(f"{' ' * (dep * 2)}- None")
            else:
                print(f"{' ' * (dep * 2)}- {node.key}")

        self.traverse(self.root, f, mode="pre")


N = int(input())
P = [int(x) - 1 for x in input().split()]

treap = Treap()
for i, p in enumerate(P):
    treap.insert_at_pos(i + 1, p)
ans = treap.to_list()
print(" ".join(map(str, ans)))

提出情報

ジャッジ結果