(TOJ) 47. 1d-kd-tree

http://sprout.tw/oj/pro/47/

其實這題主要是要讓你實作一棵二元搜尋樹啦，但是我的code不是這樣寫(delete有點麻煩XD)

如果是走二元搜尋樹，insert就是依照key值走下去就對了，query就認真找吧，delete的話，最麻煩的case是要找左子樹的max或右子樹的min。(有點籠統，抱歉~~)

我的離線(off-line)作法是，先把所有數值離散化後，開一棵數值線段樹，記錄說離散化後的這個數字有沒有出現過，沒有的話設成INF，對於每個區間，我要維護說這個區間的Max和Min。

接下來講query的部分，當如果你今天要往左子樹query的時候，右子樹的Min可能是你右邊的答案，往右子樹走的時候，左邊樹的Max可能是你的答案。

所以，綜合一下，就會發現，這題不難XDDD。

(用Treap寫也或許可以，找機會有天來試試看XDDD)

Code :
http://codepad.org/YRd2ghje