#LAI02. 動態字典統計（Dynamic Dictionary Statistics）
-
ID: 980
Type: Default
1000ms
256MiB
Tried: 3
Accepted: 0
Difficulty: 10
Uploaded By:
patricklai7528
動態字典統計（Dynamic Dictionary Statistics）
題目名稱：動態字典統計（Dynamic Dictionary Statistics）
題目背景
你負責維護一個動態字典，其 鍵 與 值 均為 64 位帶號整數（範圍 ±10¹⁸）。
資料會線上（online）抵達；每個參數都以「上一筆 有輸出 查詢結果」進行 XOR 編碼。
由於鍵的數值域極大，且對查詢延遲與記憶體有嚴格限制，你必須設計一種在最壞情況下仍能把所有操作控制在 O(log N) 時間的解法，否則會被挑戰資料擊潰。
操作說明
初始字典為空。依序處理 Q 筆操作（1 ≤ Q ≤ 300 000）：
| 代號 | 操作 | XOR 後參數含義 |
|---|---|---|
I x v |
若鍵 x 不存在則插入 (x,v)；存在則把值更新為 v |
x = raw₁ ⊕ lastAnsv = raw₂ ⊕ lastAns |
D x |
若鍵 x 存在，刪除之 |
同上（僅 1 個參數） |
C x |
輸出 嚴格小於 x 的鍵數量 |
同上 |
S x |
輸出鍵 < x 的所有值之和（若無輸出 0） |
|
K k |
輸出「第 k 小鍵」對應的值；若 k 超出範圍輸出 invalid |
k = raw ⊕ lastAns |
lastAns：上一筆有輸出查詢的結果；初值 0。I、D不產生輸出，因此不影響lastAns。- 所有計算須使用 64 位帶號整數。
輸入格式
Q
op1 arg1 [arg2]
op2 arg1 [arg2]
⋯
opQ …
- 只有
I會有兩個參數（鍵、值），其餘指令一個參數。
輸出格式
對每筆 C, S, K 查詢，各輸出一行。K 超界時輸出 invalid。
範例
輸入
10
I 5 40
I 3 10
C 4
S 6
K 2
I 7 25
D 5
C 10
S 10
K 3
輸出
1
50
40
2
35
invalid
C 4：鍵 < 4 僅 3，共 1 個。S 6：鍵 < 6 為 3, 5，其值和 10+40=50。K 2：第 2 小鍵為 5，其值 40。- … 以此類推。
限制與評分標準
| 項目 | 限制 |
|---|---|
| 時間 | 1 s |
| 記憶體 | 256 MB |
| 最大操作數 | Q = 3 × 10⁵ |
| 特殊資料 | 測試將包含長度達 3e5 的單調插入 / 刪除序列與隨機混合序列 |
要通過所有測試，你的程式 必須 令每次操作在最壞情況下保持 O(log N) 時間，並於記憶體上限內完成。