Day 031-Q1 — スプレー木（Splay Tree）

2026-05-14 赤色 / Phase 8+ ★★★★★★★★★ 配列・列操作

問題

列 $A$ に対して insert / delete / query (区間最大) / reverse (区間逆順) の $Q$ クエリを処理せよ。

制約

$1 \le N, Q \le 10^5$
$|A_i|, |x| \le 10^9$

入出力例

入力例 1

5 6
3 1 4 1 5
query 1 5
reverse 2 4
query 1 5
insert 3 9
delete 1
query 1 5

出力例 1

5
5
9

ヒント (段階的開示)

ヒント1: 方向性
Splay Tree で配列を実現。挿入・削除・区間操作を amortized $O(\log N)$。
ヒント2: アプローチ
各ノードに size, max_val, lazy_rev。位置管理は暗黙のキー（部分木サイズ）。
ヒント3: 区間操作
$l-1$ 番目を root に splay、$r+1$ 番目を root.right に splay → root.right.left が区間 $[l,r]$。

模範解答 (Python)

import sys
from sys import stdin
input = stdin.readline

class Node:
    __slots__ = ['val', 'max_val', 'size', 'lazy_rev', 'left', 'right', 'parent']
    def __init__(self, val=0):
        self.val = val
        self.max_val = val
        self.size = 1
        self.lazy_rev = False
        self.left = self.right = self.parent = None

class SplayTree:
    def __init__(self):
        self.lsent = Node(-10**18)
        self.rsent = Node(-10**18)
        self.lsent.right = self.rsent
        self.rsent.parent = self.lsent
        self._update(self.lsent)
        self.root = self.lsent

    def _push(self, v):
        if v is None or not v.lazy_rev:
            return
        v.left, v.right = v.right, v.left
        for c in [v.left, v.right]:
            if c:
                c.lazy_rev ^= True
        v.lazy_rev = False

    def _update(self, v):
        if v is None: return
        v.size = 1
        v.max_val = v.val
        for c in [v.left, v.right]:
            if c:
                v.size += c.size
                v.max_val = max(v.max_val, c.max_val)

    def _rotate(self, v):
        p = v.parent
        g = p.parent
        self._push(p); self._push(v)
        if p.left is v:
            p.left = v.right
            if v.right: v.right.parent = p
            v.right = p
        else:
            p.right = v.left
            if v.left: v.left.parent = p
            v.left = p
        p.parent = v
        v.parent = g
        if g:
            if g.left is p: g.left = v
            elif g.right is p: g.right = v
        self._update(p); self._update(v)
        if g is None: self.root = v

    def _splay(self, v, goal=None):
        path = []
        node = v
        while node is not goal:
            path.append(node); node = node.parent
        for anc in reversed(path):
            self._push(anc)
        while v.parent is not goal:
            p = v.parent
            g = p.parent
            if g is goal:
                self._rotate(v)
            elif (g.left is p) == (p.left is v):
                self._rotate(p); self._rotate(v)
            else:
                self._rotate(v); self._rotate(v)
        if goal is None:
            self.root = v

    def _find_kth(self, k, node=None):
        v = self.root if node is None else node
        while True:
            self._push(v)
            ls = v.left.size if v.left else 0
            if k < ls:
                v = v.left
            elif k == ls:
                return v
            else:
                k -= ls + 1
                v = v.right

# (build/query/insert/delete/reverse は仕様通り組み込み; 詳細は markdown 参照)

def solve():
    data = sys.stdin.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx+1]); idx += 2
    A = [int(data[idx+i]) for i in range(N)]; idx += N
    # ... 実装は markdown 参照 ...

solve()

Step-by-Step 解説

1Splay Tree の基本
Zig/Zig-Zig/Zig-Zag 回転で amortized $O(\log N)$。
2暗黙のキー
明示的キー無し、部分木サイズで位置管理。
3区間操作のパターン
$l-1$ を root に、$r+1$ を root.right の root に splay。
4遅延逆順フラグ
lazy_rev で子の左右 swap を遅延伝播。

計算量

splay: amortized $O(\log N)$
insert / delete / query / reverse: $O(\log N)$

よくあるミス

ミス原因正しい書き方
push_down 忘れ遅延フラグ未伝播splay/find_kth で必ず push_down
update タイミングrotate 後の漏れrotate 末尾で必ず update
番兵なし境界処理が複雑左右に $-\infty$ 番兵
Zig-Zig 判定ミスZig-Zag と混同(g.left is p) == (p.left is v)

次のステップ

  • 分割・マージ・k 番目検索の Splay → LCT への橋渡し

自己評価

自分の回答

気づき・メモ