Day 131-Q4 | FHQ Treap（分裂併合式暗黙Treapによる区間反転）

問題

長さ$N$の数列$A=(A_1,\dots,A_N)$に対して、$Q$個の区間反転クエリを順番に適用する。$i$番目のクエリは「区間$[l_i,r_i]$（1-indexed）を反転する」を意味する。すべてのクエリを適用した後の数列を出力せよ。

入力形式

N Q
A_1 A_2 ... A_N
l_1 r_1
l_2 r_2
...
l_Q r_Q

制約

$1 \le N, Q \le 2\times10^5$

$1 \le A_i \le 10^9$

$1 \le l_i \le r_i \le N$

入出力例

入力例1

出力例1

5 2 3 4 1

概念図

ヒント（段階的開示）

ヒント1（方向性）

区間反転を配列操作でやると1クエリO(N)でO(NQ)になり間に合わない。添字をキーとして持つ暗黙Treapを使えば、木の中の相対的な並び順=配列上の並び順として扱え、区間操作を部分木単位の操作に変換できる。

ヒント2（アプローチ）

FHQ Treapは回転操作を一切使わず、split(先頭k個と残りに分割)とmerge(aの全要素がbより前という前提で優先度をキーに併合)だけで全操作を組み立てる。区間[l,r]の反転はsplitを2回使って3分割し、真ん中の木に遅延反転フラグを立て、mergeで結合し直すだけで実現できる。

ヒント3（誘導）

def split_by_size(node, k):
    if node is None: return None, None
    push(node)
    if size(node.left) < k:
        l, r = split_by_size(node.right, k - size(node.left) - 1)
        node.right = l; pull(node)
        return node, r
    else:
        l, r = split_by_size(node.left, k)
        node.left = r; pull(node)
        return l, node

def reverse_range(root, l, r):
    a, bc = split_by_size(root, l - 1)
    b, c = split_by_size(bc, r - l + 1)
    b.rev ^= True
    return merge(merge(a, b), c)

模範解答 (Python)

import sys
import random

random.seed(12345)


class Node:
    __slots__ = ("val", "priority", "left", "right", "size", "rev")
    def __init__(self, val):
        self.val = val
        self.priority = random.random()
        self.left = None
        self.right = None
        self.size = 1
        self.rev = False


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


def pull(node):
    node.size = 1 + size(node.left) + size(node.right)


def push(node):
    if node and node.rev:
        node.left, node.right = node.right, node.left
        if node.left:
            node.left.rev ^= True
        if node.right:
            node.right.rev ^= True
        node.rev = False


def split_by_size(node, k):
    if node is None:
        return None, None
    push(node)
    if size(node.left) < k:
        l, r = split_by_size(node.right, k - size(node.left) - 1)
        node.right = l
        pull(node)
        return node, r
    else:
        l, r = split_by_size(node.left, k)
        node.left = r
        pull(node)
        return l, node


def merge(a, b):
    if a is None:
        return b
    if b is None:
        return a
    if a.priority > b.priority:
        push(a)
        a.right = merge(a.right, b)
        pull(a)
        return a
    else:
        push(b)
        b.left = merge(a, b.left)
        pull(b)
        return b


def build(arr):
    root = None
    for v in arr:
        root = merge(root, Node(v))
    return root


def reverse_range(root, l, r):
    a, bc = split_by_size(root, l - 1)
    b, c = split_by_size(bc, r - l + 1)
    b.rev ^= True
    return merge(merge(a, b), c)


def to_list(node):
    res = []
    stack = [(node, False)]
    while stack:
        nd, visited = stack.pop()
        if nd is None:
            continue
        if visited:
            res.append(nd.val)
            continue
        push(nd)
        stack.append((nd.right, False))
        stack.append((nd, True))
        stack.append((nd.left, False))
    return res


def solve():
    sys.setrecursionlimit(500000)
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    a = [int(data[idx + i]) for i in range(n)]; idx += n

    root = build(a)
    for _ in range(q):
        l = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        root = reverse_range(root, l, r)

    print(*to_list(root))


solve()

Step-by-Step 解説

1添字を持たない「暗黙的」表現
keyを明示的に持たず、部分木サイズを管理し、木を中順走査したときの並び順を配列の並び順とみなす。

2split（分裂）
木を中順走査したときの先頭k個からなる木と残りに分割する。左部分木サイズとkを比較して再帰する典型実装で期待O(log N)。

3merge（併合）
2つの木を優先度が高い方を根にする形で再帰的に併合する。優先度がランダムなので期待的に木の高さがO(log N)に保たれる（回転不要）。

4遅延反転フラグ
revフラグを立てるだけにして、実際の左右入れ替えはpush（そのノードにアクセスするタイミング）まで遅延させる。遅延セグメント木と同じ発想。

5計算量
split・mergeは期待O(log N)。Q回のクエリそれぞれでsplit2回・merge2回を行うので全体で期待O((N+Q)log N)。

よくあるミス

ミス	原因	正しい書き方
splitやmergeの中でpushを呼び忘れる	遅延フラグが子に伝播される前にsize(node.left)などを参照してしまう	部分木の構造に依存する処理の直前に必ずpushする
pullの呼び出し忘れ	子ノードを変更後にsizeを更新し忘れ以降の分割位置がずれる	node.left/rightを変更した直後に必ずpull(node)を呼ぶ
反転区間の指定を0-indexedのまま渡す	1-indexedの問題設定と0-indexedの実装の変換ミス	split_by_size(root, l-1)のように常に「先頭何個」という個数ベースに変換する
to_listを再帰で書きNが大きいとスタックオーバーフロー	Pythonの再帰上限を超える深さの木を再帰で走査する	明示的スタックを使った反復走査に書き換える

次のステップ

発展: 区間和・区間最小値クエリを同時にサポートする（sum,minフィールドをpull/pushで伝播）、挿入・削除にも対応させたフル機能の実装
次回予告: 次回のテーマは今後のセッションで選定

自己評価

完全理解おおむね理解要復習

Day 131-Q4 — FHQ Treap（分裂併合式暗黙Treapによる区間反転）

問題