Day 068-Q1 — 暗黙的Treap（Implicit Treap・区間逆転・列操作）

問題

長さ $N$ の整数列 $A = [a_1, a_2, \ldots, a_N]$ に対し、$Q$ 個のクエリを処理せよ。

• クエリ型 1: 1 l r — $A[l..r]$（1-indexed, 閉区間）を逆順にする。
• クエリ型 2: 2 l r — $A[l..r]$ の最大値を出力する。
• クエリ型 3: 3 i v — $A[i]$ を $v$ に変更する。

入出力例

6 5
3 1 4 1 5 9
1 2 5
2 1 6
3 3 7
1 1 6
2 2 5

9
7

1 2 5 後: [3,5,1,4,1,9]。最大=9。3 3 7 後: [3,5,7,4,1,9]。1 1 6 後: [9,1,4,7,5,3]。2 2 5 → max(1,4,7,5)=7。

概念図: Implicit Treap の split/merge

ヒント（段階的開示）

def push_down(t):
    if t and t.rev:
        t.left, t.right = t.right, t.left
        if t.left:  t.left.rev  ^= True
        if t.right: t.right.rev ^= True
        t.rev = False

def split(t, k):
    if t is None: return None, None
    push_down(t)
    lsz = sz(t.left)
    if lsz >= k:
        l, t.left = split(t.left, k)
        pull_up(t); return l, t
    else:
        t.right, r = split(t.right, k - lsz - 1)
        pull_up(t); return t, r

模範解答 (Python)

コピーimport sys
import random
input = sys.stdin.readline

class Node:
    __slots__ = ['val','pri','sz','mx','rev','left','right']
    def __init__(self, val):
        self.val = val
        self.pri = random.random()
        self.sz = 1
        self.mx = val
        self.rev = False
        self.left = self.right = None

def _sz(t): return t.sz if t else 0
def _mx(t): return t.mx if t else -1

def push_down(t):
    if t and t.rev:
        t.left, t.right = t.right, t.left
        if t.left:  t.left.rev  ^= True
        if t.right: t.right.rev ^= True
        t.rev = False

def pull_up(t):
    if t:
        t.sz = 1 + _sz(t.left) + _sz(t.right)
        t.mx = max(t.val, _mx(t.left), _mx(t.right))

def split(t, k):
    if t is None:
        return None, None
    push_down(t)
    lsz = _sz(t.left)
    if lsz >= k:
        l, t.left = split(t.left, k)
        pull_up(t)
        return l, t
    else:
        t.right, r = split(t.right, k - lsz - 1)
        pull_up(t)
        return t, r

def merge(l, r):
    if l is None: return r
    if r is None: return l
    push_down(l); push_down(r)
    if l.pri > r.pri:
        l.right = merge(l.right, r)
        pull_up(l)
        return l
    else:
        r.left = merge(l, r.left)
        pull_up(r)
        return r

def main():
    sys.setrecursionlimit(500000)
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    root = None
    for v in A:
        root = merge(root, Node(v))

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        if line[0] == 1:
            _, l, r = line
            l -= 1
            t1, t2 = split(root, l)
            t2, t3 = split(t2, r - l)
            t2.rev ^= True
            root = merge(t1, merge(t2, t3))
        elif line[0] == 2:
            _, l, r = line
            l -= 1
            t1, t2 = split(root, l)
            t2, t3 = split(t2, r - l)
            out.append(_mx(t2))
            root = merge(t1, merge(t2, t3))
        else:
            _, i, v = line
            i -= 1
            t1, t2 = split(root, i)
            t2, t3 = split(t2, 1)
            t2.val = v
            pull_up(t2)
            root = merge(t1, merge(t2, t3))

    print('\n'.join(map(str, out)))

main()

Step-by-Step 解説

Step 1: 暗黙的 Treap の基本構造

Treap はランダム優先度 pri で heap 性質を持つ BST。「暗黙的」とは添字をキーとせず、sz（部分木サイズ）から暗黙に位置を計算する点。これにより「k番目の要素」へのアクセスが $O(\log N)$ で可能になる。

Step 2: split(t, k) の動作

左部分木サイズ lsz = sz(t.left) と k を比較する。

Step 3: 遅延反転フラグ

t.rev = True はこのノードの部分木が逆順になっていることを示す遅延フラグ。push_down 時に左右子を交換し、子に rev を伝播させることで $O(\log N)$ で区間逆転が実現する。

Step 4: クエリ処理フロー

Step 5: 計算量

よくあるミス

次のステップ

発展問題: 暗黙的 Treap で区間ソート（マージソートとの融合）、または永続 Treap（バージョン管理）。関連: RBST（Randomized BST）との比較実装。

自己評価