問題
$N$ 要素の列 $A$ に対し、以下の $Q$ 個のクエリをオンラインで処理せよ：
reverse l r: $A[l..r]$（1-indexed, 両端含む）を逆順にするquery l r: $A[l..r]$ の総和を出力するupdate i x: $A[i] \leftarrow x$
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 2 \times 10^5$ |
| $Q$ | $1 \le Q \le 2 \times 10^5$ |
| $|A_i|, |x|$ | $\le 10^9$ |
| $l, r, i$ | $1 \le l \le r \le N$、$1 \le i \le N$ |
入出力例
入力例 1
5
1 2 3 4 5
5
query 1 5
reverse 2 4
query 1 5
update 3 10
query 1 5出力例 1
15
15
22初期 [1,2,3,4,5]。query → 15。reverse 2 4 → [1,4,3,2,5]。query → 15（変わらず）。update 3 10 → [1,4,10,2,5]。query → 22。
概念図: 暗黙的Treap の split / merge / reverse
ヒント（段階的開示）
ヒント1: 方向性
暗黙的 Treap (Implicit Treap) はキーをインデックスとして扱う平衡二分探索木。各ノードに部分木サイズ (sz) を持ち、split/merge で列の任意区間を $O(\log N)$ 期待値で操作できる。遅延反転フラグ (rev) で区間反転をサポートする。
ヒント2: アプローチ
split(t, k): 先頭 k 要素と残りに分割。左部分木サイズlsと k を比較して再帰。merge(l, r): 優先度で根を決定し再帰的に結合。push_down(t):rev=Trueのとき左右子を swap し、子にrev XOR= True。- 全操作は split×2 → 操作 → merge×2 の形で実装できる。
ヒント3: コード骨格
class Node:
__slots__ = ['val','s','sz','pri','l','r','rev']
def __init__(self, v):
self.val=v; self.s=v; self.sz=1
self.pri=random.getrandbits(32)
self.l=self.r=None; self.rev=False
def _down(t): # push_down
if t and t.rev:
t.l, t.r = t.r, t.l
if t.l: t.l.rev ^= True
if t.r: t.r.rev ^= True
t.rev = False
def split(t, k): # left k, rest
if not t: return None, None
_down(t)
ls = _sz(t.l)
if k <= ls:
ll, lr = split(t.l, k)
t.l = lr; _up(t); return ll, t
else:
rl, rr = split(t.r, k-ls-1)
t.r = rl; _up(t); return t, rr模範解答 (Python)
import sys, random
input = sys.stdin.readline
sys.setrecursionlimit(500000)
class Node:
__slots__ = ['val','s','sz','pri','l','r','rev']
def __init__(self, v):
self.val=v; self.s=v; self.sz=1
self.pri=random.getrandbits(32)
self.l=self.r=None; self.rev=False
def _sz(t): return t.sz if t else 0
def _s(t): return t.s if t else 0
def _up(t):
if t:
t.sz = 1+_sz(t.l)+_sz(t.r)
t.s = t.val+_s(t.l)+_s(t.r)
def _down(t):
if t and t.rev:
t.l, t.r = t.r, t.l
if t.l: t.l.rev ^= True
if t.r: t.r.rev ^= True
t.rev = False
def merge(l, r):
if not l: return r
if not r: return l
_down(l); _down(r)
if l.pri > r.pri:
l.r = merge(l.r, r); _up(l); return l
else:
r.l = merge(l, r.l); _up(r); return r
def split(t, k):
if not t: return None, None
_down(t)
ls = _sz(t.l)
if k <= ls:
ll, lr = split(t.l, k)
t.l = lr; _up(t); return ll, t
else:
rl, rr = split(t.r, k-ls-1)
t.r = rl; _up(t); return t, rr
def main():
N = int(input())
A = list(map(int, input().split()))
root = None
for v in A:
root = merge(root, Node(v))
Q = int(input())
out = []
for _ in range(Q):
line = input().split()
op = line[0]
if op == 'reverse':
l, r = int(line[1])-1, int(line[2])-1
a, bc = split(root, l)
b, c = split(bc, r-l+1)
if b: b.rev ^= True
root = merge(merge(a, b), c)
elif op == 'query':
l, r = int(line[1])-1, int(line[2])-1
a, bc = split(root, l)
b, c = split(bc, r-l+1)
out.append(str(_s(b)))
root = merge(merge(a, b), c)
else: # update
i, x = int(line[1])-1, int(line[2])
a, bc = split(root, i)
b, c = split(bc, 1)
if b: b.val=x; b.s=x
root = merge(merge(a, b), c)
print('\n'.join(out))
main()Step-by-Step 解説
Step 1: 暗黙的キーの概念
通常の BST はキー値で大小比較するが、暗黙的Treap では「左部分木のサイズ」を使って位置を計算する。sz を更新し続けることで、任意の位置に $O(\log N)$ でアクセスできる。
Step 2: split(t, k) — 先頭 k 要素と残りに分割
左部分木サイズ ls = sz(t.left) を見る：k ≤ ls なら分割点は左部分木内、そうでなければ右部分木内。必ず _down(t) で lazy を先に伝播させる。
Step 3: 遅延反転 (rev lazy)
reverse(l, r) は split3 で中央を取り出し、b.rev ^= True でフラグを立てるだけ。実際の swap は次に _down(b) が呼ばれるときに遅延実行される。
Step 4: merge の優先度管理
max-heap 的に priority の高い方を根にすることで、木の高さが $O(\log N)$ 期待値になる。priority は一様乱数で割り当てる。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| push_down を忘れる | rev フラグが伝播せず誤動作 | split/merge の冒頭で必ず _down(t) |
| split 後に root が変わることを忘れる | 分割後に古い root を使う | split/merge は常に新しい root を返す |
update で b.s の更新漏れ | val を変更したが s が古い | b.val=x; b.s=x（葉なのでszは1のまま） |
| 1-indexed と 0-indexed の混乱 | split(root, l-1) と書くべきところを split(root, l) にする | 0-indexed に変換してから split に渡す |
次のステップ
- 発展問題: 区間への一定値加算（add_lazy を追加）、区間最大値クエリ
- 関連: Splay Tree（Treap と同じ操作を最悪 $O(\log N)$ amortized で行う）