Day 046-Q2 — 平衡二分木上の遅延伝播（暗黙的Treap・区間反転）

2026-05-30 赤色 Master / Phase 8+ ★★★★★★★★★ Implicit Treap / 遅延反転 / 区間和

問題

長さ $N$ の整数列 $a_1, \ldots, a_N$ に対して以下の操作をオンラインで $Q$ 回処理せよ：

  • 1 l r：$a_l, \ldots, a_r$ の区間を反転（reverse）する
  • 2 l r：$a_l, \ldots, a_r$ の総和を出力する

制約

$1 \le N, Q \le 2 \times 10^5$
$-10^9 \le a_i \le 10^9$
$1 \le l \le r \le N$
時間制限: 2秒

入出力例

入力例 1

6 4
1 2 3 4 5 6
2 1 6
1 2 5
2 1 6
2 3 5

出力例 1

21
21
12

概念図: 暗黙的Treapの split / merge

元の列: [1, 2, 3, 4, 5, 6] split(root, 1) → t1=[1], tmp=[2,3,4,5,6] split(tmp, 4) → t2=[2,3,4,5], t3=[6] t1=[1] sum=1 t2=[2,3,4,5] rev=True sum=14 (反転フラグON) t3=[6] sum=6 → merge(t1, merge(t2, t3)) 結果列: [1, 5, 4, 3, 2, 6] push_down: rev=True の時、左右子を swap し子に rev フラグを XOR 伝播 各ノードは (val, sum, size, pri, rev, left, right) を保持 split/merge は O(log N) で動作。区間反転は split×2 + rev ^= True + merge×2 sum は反転しても変わらないため total sum クエリも O(log N)

ヒント（段階的開示）

ヒント1: 方向性
通常のセグメント木では区間反転を $O(\log N)$ で処理できません。配列の順序を管理できる暗黙的 Treap（implicit key Treap）を使いましょう。
ヒント2: アプローチ
  • 暗黙的Treap: キーが添字順 = subtree_size による位置管理
  • 各ノードに rev フラグ（遅延反転）を持たせる
  • split(t, k): 先頭 $k$ 要素 / 残り に分割
  • merge(l, r): 2つのTreapを連結
  • 反転: split 2回 → 中間部の rev フラグを反転 → merge 2回
  • push_down 時に左右子を swap して rev フラグを伝播
ヒント3: push_down / update の骨格 
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 update(t):
    if t:
        t.size = sz(t.left) + 1 + sz(t.right)
        t.sum  = sm(t.left) + t.val + sm(t.right)

模範解答 (Python)

import sys
import random
sys.setrecursionlimit(400000)
input = sys.stdin.readline

class Node:
    __slots__ = ('val','sum','size','pri','rev','left','right')
    def __init__(self, v):
        self.val = v
        self.sum = v
        self.size = 1
        self.pri = random.random()
        self.rev = False
        self.left = None
        self.right = None

def sz(t): return t.size if t else 0
def sm(t): return t.sum  if t else 0

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 update(t):
    if t:
        t.size = sz(t.left) + 1 + sz(t.right)
        t.sum  = sm(t.left) + t.val + sm(t.right)

def split(t, k):
    if not t:
        return None, None
    push_down(t)
    left_size = sz(t.left)
    if left_size >= k:
        l, t.left = split(t.left, k)
        update(t)
        return l, t
    else:
        t.right, r = split(t.right, k - left_size - 1)
        update(t)
        return t, r

def merge(l, r):
    if not l: return r
    if not r: return l
    push_down(l); push_down(r)
    if l.pri > r.pri:
        l.right = merge(l.right, r)
        update(l)
        return l
    else:
        r.left = merge(l, r.left)
        update(r)
        return r

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

def main():
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))
    root = build(a)

    out = []
    for _ in range(Q):
        line = list(map(int, input().split()))
        op, l, r = line[0], line[1] - 1, line[2] - 1
        t1, tmp = split(root, l)
        t2, t3  = split(tmp, r - l + 1)
        if op == 1:
            t2.rev ^= True
        else:
            out.append(sm(t2))
        root = merge(t1, merge(t2, t3))

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

main()

Step-by-Step 解説

1暗黙的Treapの概念
Treapのキーを「配列添字」として暗黙的に管理する。各ノードは subtree_size を持ち、split(t,k) で位置 $k$ を境に分割する。
2遅延反転フラグ
rev=True は「この部分木を反転すること」を遅延。push_down で左右子を swap し、フラグを子に XOR 伝播。
3split 操作 $O(\log N)$
push_down してから左部分木サイズと比較して再帰的に分割。
4merge 操作 $O(\log N)$
優先度（乱数）を比較して大きい方を根にし、再帰的に結合。
5区間反転クエリ $O(\log N)$
split 2回で区間を取り出し、rev ^= True して merge 2回で戻す。sum は反転しても不変。

計算量

split / merge: $O(\log N)$ 期待値
区間反転: $O(\log N)$
区間和: $O(\log N)$
空間: $O(N)$

よくあるミス

ミス原因正しい書き方
push_down を操作前に忘れるrev フラグが伝播されず不正必ず操作前に push_down(t)
update の呼び忘れsize/sum が古い値のままmerge/split の最後に update(t)
再帰深度オーバーPython デフォルト 1000sys.setrecursionlimit(400000)
空ノードの sum/size アクセスNoneType エラーsz(t), sm(t) で None チェック

次のステップ

  • 発展問題: 区間反転に加えて区間加算・区間乗算も Treap で処理する
  • 関連: Day031 Q1 スプレー木（Splay Tree）との比較
  • 応用: 文字列の区間コピー・挿入・削除操作

自己評価