問題
オンラインクエリ（前の出力で XOR 復号）: INSERT x, DELETE x, KMIN k, COUNT x, MERGE k1 k2。
制約
$1 \le Q \le 2 \times 10^5$
$x, k \le 10^9$
入出力例
入力例 1
5
INSERT 10
INSERT 20
INSERT 15
KMIN 2
COUNT 15出力例 1
15
2ヒント (段階的開示)
ヒント1: 方向性
Treap（BST 順 + heap 順のランダム優先度）で期待深さ $O(\log N)$。各ノードに
size を持たせて順序統計を実現。ヒント2: アプローチ
主要操作:
split_by_key, split_by_size, merge。これらで insert/delete/kth_min/count を実装。ヒント3: 誘導
XOR 復号:
x = (raw ^ last_ans) % MOD。模範解答 (Python)
import sys
import random
input = sys.stdin.readline
sys.setrecursionlimit(300000)
random.seed(42)
class Node:
__slots__ = ['key', 'pri', 'left', 'right', 'size']
def __init__(self, key):
self.key = key
self.pri = random.getrandbits(32)
self.left = None
self.right = None
self.size = 1
def size(t):
return t.size if t else 0
def update(t):
if t:
t.size = 1 + size(t.left) + size(t.right)
def merge(l, r):
if l is None: return r
if r is None: return l
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 split_by_key(t, key):
if t is None: return None, None
if t.key < key:
l, r = split_by_key(t.right, key)
t.right = l; update(t); return t, r
else:
l, r = split_by_key(t.left, key)
t.left = r; update(t); return l, t
def split_by_size(t, k):
if t is None: return None, None
lsize = size(t.left)
if lsize >= k:
l, r = split_by_size(t.left, k)
t.left = r; update(t); return l, t
else:
l, r = split_by_size(t.right, k - lsize - 1)
t.right = l; update(t); return t, r
def insert(t, key):
node = Node(key)
l, r = split_by_key(t, key)
return merge(merge(l, node), r)
def delete(t, key):
if t is None: return None
if t.key == key:
return merge(t.left, t.right)
elif key < t.key:
t.left = delete(t.left, key)
else:
t.right = delete(t.right, key)
update(t); return t
def kth_min(t, k):
lsize = size(t.left)
if k <= lsize: return kth_min(t.left, k)
elif k == lsize + 1: return t.key
else: return kth_min(t.right, k - lsize - 1)
def count_leq(t, x):
if t is None: return 0
if t.key <= x:
return size(t.left) + 1 + count_leq(t.right, x)
else:
return count_leq(t.left, x)
def solve():
Q = int(input())
root = None
last_ans = 0
MOD = 10**9 + 7
out = []
for _ in range(Q):
line = input().split()
op = line[0]
if op == 'INSERT':
x = (int(line[1]) ^ last_ans) % MOD
root = insert(root, x)
elif op == 'DELETE':
x = (int(line[1]) ^ last_ans) % MOD
root = delete(root, x)
elif op == 'KMIN':
k = (int(line[1]) ^ last_ans) % MOD
if k < 1 or k > size(root):
out.append(-1); last_ans = -1
else:
ans = kth_min(root, k); out.append(ans); last_ans = ans
elif op == 'COUNT':
x = (int(line[1]) ^ last_ans) % MOD
ans = count_leq(root, x); out.append(ans); last_ans = ans
elif op == 'MERGE':
k1 = (int(line[1]) ^ last_ans) % MOD
k2 = (int(line[2]) ^ last_ans) % MOD
if k1 > size(root):
out.append(-1); last_ans = -1
else:
l, r = split_by_size(root, k1)
if k2 < 1 or k2 > size(r):
out.append(-1); last_ans = -1
root = merge(l, r)
else:
ans = kth_min(r, k2); out.append(ans); last_ans = ans
root = merge(l, r)
print('\n'.join(map(str, out)))
solve()Step-by-Step 解説
1Treap 構造
BST + max-heap（優先度はランダム）。期待深さ $O(\log N)$。
BST + max-heap（優先度はランダム）。期待深さ $O(\log N)$。
2merge/split
merge は優先度高い方を根、split はキーまたはサイズで分割。
merge は優先度高い方を根、split はキーまたはサイズで分割。
3順序統計
各ノードに
各ノードに
size。kth_min, count_leq ともに $O(\log N)$。4オンライン処理
(raw ^ last_ans) % MOD でクエリ復号。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| size の更新忘れ | merge/split 後 update なし | 全ての変更後に update(t) |
| split_by_size 境界 | lsize と k の比較 | lsize >= k → 左 |
| 再帰制限超過 | Python デフォルト | sys.setrecursionlimit(300000) |
次のステップ
- Implicit Treap + lazy（区間反転・区間和）
- AVL / 赤黒木 / スキップリスト比較