解法：相信大家都會寫持久化線段樹的作法，我就不介紹了
今天用的是一種叫劃分樹的資料結構，感覺是中國選手自己搞出來的東西
因為找不到英文的資料
倒是 google 的到很多簡體中文資料
隨便貼其中一個划分树 - pony1993 - 博客园，說明應該比我清楚

劃分樹可視為一種線段樹，但每個結點存的是一段子序列\([l,r]\)
每個節點的左孩子依序儲存該區間 \(\le\) 中位數的數
右孩子依序儲存該區間 \(\ge\) 中位數的數
為了二分區間，跟中位數相等的數的要特別處理
使得兩孩子的區間長度差 \(\le\) 1
同時，每個節點也儲存一個陣列 \(cnt\)
\(cnt[i] = [l..i]\) 中有多少元素進入左子樹

有了 \(cnt\) 陣列後不難推出查詢方法