46 . 1d-kd-tree
TopCoder
Description
廢話不多說(X)，請你維護一個集合 $P$ ，一開始集合為空，所有操作都在一維的數線上。現在給你 $N$ 個操作，操作有三種：
insert$x$：加入一點座標為 $x$ 到當前的集合內。delete$x$ ：從集合內將點座標為 $x$ 的點刪除，該操作出現時保證點 $x$ 已經在集合內。query$x$：詢問在目前集合中，距離座標 $x$ 最近的點座標為多少，請輸出一行包含一個整數代表距離 $x$ 最近的點座標；若同時存在兩個不同的座標距離 $x$ 一樣近，請輸出這兩個座標，較小的先輸出。詢問時保證集合內至少有一個點。
Input Format
輸入的第一行包含一個整數 $N\,(N \leq 10 ^ 5)$，代表接下來有 $N$ 筆操作。操作的格式前面題目敘述所述。
保證 $|x| \leq 10 ^ 9$，測資是隨機產生的，你可以假設你產生的二元樹不會不夠平衡。
Output Format
遇到操作為 query $x$ 時輸出一行詢問的結果。
Sample Input 1
7
insert 4
insert 10
insert 5
query 7
delete 5
query 7
query 10
insert 4
insert 10
insert 5
query 7
delete 5
query 7
query 10
Sample Output 1
5
4 10
10
4 10
10
Hints
Problem Source
NEOJ Problem 47
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | $N\leq 1000$ | 30 |
| 2 | 3~9 | 無額外限制。 | 70 |