一維KD樹
題目敘述
請你維護一個集合 $P$ ,一開始集合為空,所有操作都在一維的數線上。現在給你 $N$ 個操作,操作有三種:
- insert x:加入一點座標為 $x$ 到當前的集合內。
- delete x:從集合內將點座標為 $x$ 的點刪除,該操作出現時保證點 $x$ 已經在集合內。
- query x:詢問在目前集合中,距離座標 $x$ 最近的點座標為多少,請輸出一行包含一個整數代表距離 $x$ 最近的點座標;若同時存在兩個不同的座標距離 $x$ 一樣近,請輸出這兩個座標,較小的先輸出。詢問時保證集合內至少有一個點。
輸入說明
輸入的第一行包含一個整數 $N(N\leq 10^5)$,代表接下來有 $N$ 筆操作。操作的格式前面題目敘述所述,保證$|x| \leq 10^9$
測資是隨機產生的,你可以假設你產生的二元樹不會不夠平衡。
輸出說明
遇到操作為 query x
時輸出一行詢問的結果。
範例輸入
範例輸出
子題一[30%]
$N\leq 1000$
子題二[70%]
上述子題的條件不再成立。
Judge Setting
run-time limit: 150 ms
memory limit: 512000 byte
測資數量: 0