lessons/互动程序/11-平衡树/00-把一段话翻过来.py

#!/usr/bin/env python3
"""课前零食：带双哨兵、rev Lazy 的隐式 Splay 小实验室。"""

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class Node:
    label: str
    value: int
    left: Node | None = None
    right: Node | None = None
    parent: Node | None = None
    size: int = 1
    total: int = 0
    rev: bool = False

    def __post_init__(self) -> None:
        self.total = self.value


def node_size(node: Node | None) -> int:
    return node.size if node else 0


def node_sum(node: Node | None) -> int:
    return node.total if node else 0


class SequenceSplay:
    def __init__(self) -> None:
        self.model = list("ABCDEF")
        labels = ["L"] + self.model + ["R"]
        values = [0, 10, 20, 30, 40, 50, 60, 0]
        nodes = [Node(label, value) for label, value in zip(labels, values)]
        self.root = self.build_balanced(nodes)

    def build_balanced(self, nodes: list[Node]) -> Node | None:
        if not nodes:
            return None
        middle = len(nodes) // 2
        root = nodes[middle]
        root.left = self.build_balanced(nodes[:middle])
        root.right = self.build_balanced(nodes[middle + 1 :])
        if root.left:
            root.left.parent = root
        if root.right:
            root.right.parent = root
        self.pull(root)
        return root

    def pull(self, node: Node | None) -> None:
        if node:
            node.size = 1 + node_size(node.left) + node_size(node.right)
            node.total = node.value + node_sum(node.left) + node_sum(node.right)

    def apply_rev(self, node: Node | None) -> None:
        if node is None:
            return
        node.left, node.right = node.right, node.left
        node.rev = not node.rev

    def push(self, node: Node | None) -> None:
        if node and node.rev:
            self.apply_rev(node.left)
            self.apply_rev(node.right)
            node.rev = False

    def push_path(self, node: Node) -> None:
        chain: list[Node] = []
        current: Node | None = node
        while current:
            chain.append(current)
            current = current.parent
        for ancestor in reversed(chain):
            self.push(ancestor)

    def is_right(self, node: Node) -> bool:
        return node.parent is not None and node.parent.right is node

    def rotate(self, node: Node, log: list[str]) -> None:
        parent = node.parent
        if parent is None:
            return
        grand = parent.parent
        if node is parent.left:
            middle = node.right
            node.right = parent
            parent.left = middle
            direction = "右旋"
        else:
            middle = node.left
            node.left = parent
            parent.right = middle
            direction = "左旋"
        if middle:
            middle.parent = parent
        parent.parent = node
        node.parent = grand
        if grand is None:
            self.root = node
        elif parent is grand.left:
            grand.left = node
        else:
            grand.right = node
        self.pull(parent)
        self.pull(node)
        log.append(f"{direction}：{node.label} 绕 {parent.label}。")

    def splay(self, node: Node, goal: Node | None, log: list[str]) -> None:
        self.push_path(node)
        while node.parent is not goal:
            parent = node.parent
            if parent is None:
                break
            grand = parent.parent
            if grand is goal:
                self.rotate(node, log)
            elif self.is_right(node) == self.is_right(parent):
                self.rotate(parent, log)
                self.rotate(node, log)
            else:
                self.rotate(node, log)
                self.rotate(node, log)

    def kth(self, rank: int) -> Node:
        if not 1 <= rank <= node_size(self.root):
            raise ValueError("排名越界")
        current = self.root
        while current:
            self.push(current)
            left_count = node_size(current.left)
            if rank <= left_count:
                current = current.left
            elif rank == left_count + 1:
                return current
            else:
                rank -= left_count + 1
                current = current.right
        raise RuntimeError("size 账本损坏")

    def expose(self, left: int, right: int) -> tuple[Node, Node, Node, list[str]]:
        if not (1 <= left <= right <= len(self.model)):
            raise ValueError("区间应满足 1 ≤ l ≤ r ≤ 当前长度")
        log: list[str] = []
        x = self.kth(left)
        log.append(f"x=kth({left})={x.label}，先伸到根。")
        self.splay(x, None, log)
        y = self.kth(right + 2)
        log.append(f"y=kth({right + 2})={y.label}，再伸到 x 的右儿子位置。")
        self.splay(y, x, log)
        mid = y.left
        if mid is None:
            raise RuntimeError("合法非空区间不应暴露为空")
        return x, y, mid, log

    def reverse(self, left: int, right: int) -> list[str]:
        x, y, mid, log = self.expose(left, right)
        self.apply_rev(mid)
        self.pull(y)
        self.pull(x)
        self.model[left - 1 : right] = reversed(self.model[left - 1 : right])
        log.append(f"对 y.left={mid.label} 的子树 apply_rev；不逐项移动字符。")
        return log

    def interval_sum(self, left: int, right: int) -> tuple[int, list[str]]:
        _, _, mid, log = self.expose(left, right)
        log.append(f"读取 mid.sum={mid.total}。")
        return mid.total, log

    def inorder_nodes(self, node: Node | None = None, top: bool = True) -> list[Node]:
        if top:
            node = self.root
        if node is None:
            return []
        self.push(node)
        return self.inorder_nodes(node.left, top=False) + [node] + self.inorder_nodes(node.right, top=False)

    def body_labels(self) -> list[str]:
        return [node.label for node in self.inorder_nodes()[1:-1]]

    def body_values(self) -> list[int]:
        return [node.value for node in self.inorder_nodes()[1:-1]]

    def show(self) -> None:
        nodes = self.inorder_nodes()
        print("完整中序：", " ".join(node.label for node in nodes))
        print("正文：", " ".join(self.body_labels()))
        print("正文数值：", self.body_values())
        print("提示：L、R 只占位置，不计正文答案。")

    def check(self) -> tuple[bool, str]:
        def dfs(node: Node | None, parent: Node | None) -> tuple[bool, int, int, str]:
            if node is None:
                return True, 0, 0, ""
            self.push(node)
            if node.parent is not parent:
                return False, 0, 0, f"{node.label} 的 parent 指针错误"
            ok_l, left_size, left_sum, why = dfs(node.left, node)
            if not ok_l:
                return False, 0, 0, why
            ok_r, right_size, right_sum, why = dfs(node.right, node)
            if not ok_r:
                return False, 0, 0, why
            expected_size = left_size + 1 + right_size
            expected_sum = left_sum + node.value + right_sum
            if node.size != expected_size or node.total != expected_sum:
                return False, 0, 0, f"{node.label} 的 size/sum 摘要错误"
            return True, expected_size, expected_sum, ""
        ok, _, _, why = dfs(self.root, None)
        if not ok:
            return False, why
        if self.body_labels() != self.model:
            return False, f"树中正文 {self.body_labels()} 与列表验算 {self.model} 不同"
        return True, "parent、size、sum、Lazy 后的逻辑序列均正确"


def print_log(log: list[str]) -> None:
    for line in log:
        print(" ", line)


def warmup() -> None:
    print("=== 任务 0：先预测双哨兵的夹子 ===")
    print("正文为 A B C D E F，目标区间是 [2,5]。")
    try:
        input("请先写 x=kth(l) 和 y=kth(r+2) 分别是谁，再按回车： ")
    except EOFError:
        pass
    print("核对：x=A，y=F；B,C,D,E 会成为 y.left。")


def main() -> None:
    sequence = SequenceSplay()
    print("文艺平衡树小实验室：隐式 Splay + 双哨兵 + rev Lazy。")
    warmup()
    sequence.show()
    print("\n命令：show；expose 2 5；rev 2 5；sum 2 5；check；q。")
    while True:
        try:
            raw = input("\n> ").strip()
        except EOFError:
            raw = "q"
        if not raw or raw in {"q", "quit", "exit"}:
            return
        parts = raw.split()
        try:
            if parts == ["show"]:
                sequence.show()
            elif parts == ["check"]:
                ok, message = sequence.check()
                print("通过：" if ok else "失败：", message)
            elif len(parts) == 3 and parts[0] == "expose":
                left, right = int(parts[1]), int(parts[2])
                x, y, mid, log = sequence.expose(left, right)
                print_log(log)
                print(f"暴露完成：x={x.label}，y={y.label}，y.left 的根是 {mid.label}。")
                print("y.left 的中序：", " ".join(node.label for node in sequence.inorder_nodes(mid, top=False)))
            elif len(parts) == 3 and parts[0] == "rev":
                print_log(sequence.reverse(int(parts[1]), int(parts[2])))
                sequence.show()
            elif len(parts) == 3 and parts[0] == "sum":
                answer, log = sequence.interval_sum(int(parts[1]), int(parts[2]))
                print_log(log)
                print("区间和：", answer)
            else:
                raise ValueError
        except ValueError as error:
            print("小提示：", error or "试试 rev 2 5。")


if __name__ == "__main__":
    main()