又是区间第k大，这次选择这道题是为以后写线段树套平衡树铺路的。Range Tree可以理解成线段树套vector吧，相当于每个结点多存了对应区间的一个排好序的序列。画一下就会知道空间的消耗是nlogn的。然后我们只需要二分答案就可以了，二分的时候相当于是在logn个不相交的小区间里询问<=mid的有多少个，所以这里会有一个logn*logn。然后总的话我们要二分答案，所以每次询问的时间复杂度是logn*logn*logn. 它的好处在于我们不需要离散化了，这和划分树一样显得非常的好嘛。
这道题具有启发性是因为当区间第k大支持点修改的时候我们只需要将vector换成另外一种数据结构，一棵平衡树就可以了。因为多了修改，所以每次修改我们会涉及到logn个结点对应的修改，平衡树上删一个点，插一个点的复杂度是logn，所以每次修改都是logn*logn,然后就要考虑查询了，查询是一样的，只要平衡树支持询问<=mid的有多少个数就可以了，最后仍然是一个(logn)^3.
但是由于STL里的multiset等已经写好的树状结构并不支持O（logn）询问比某个数小的有多少个的这个操作，所以平衡树就被迫自己写了，这个我后面再研究研究吧。下面的代码参考了挑战程序设计竞赛的P188,P189。因为是logn^3所以速度达到7000ms，跟划分树和函数式线段树自然就没得比啦。
#pragma warning(disable:4996)#include#include #include #include #include #include #define maxn 100000using namespace std;vector dat[4*maxn + 50];int a[maxn + 50];int n, q;void build(int k, int l, int r){ if (r - l == 1) { dat[k].push_back(a[l]); return; } int lc = k << 1, rc = k << 1 | 1; build(lc, l, (l + r) / 2); build(rc, (l + r) / 2, r); dat[k].resize(r - l); merge(dat[lc].begin(), dat[lc].end(), dat[rc].begin(), dat[rc].end(),dat[k].begin());}//[i,j)里<=x的有多少个int query(int i,int j,int x,int k,int l,int r){ if (j <= l || r <= i) return 0; else if (i <= l&&r <= j){ return upper_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin(); } else { int lcnt = query(i, j, x, k << 1, l, (l + r) / 2); int rcnt = query(i, j, x, k << 1 | 1, (l + r) / 2, r); return lcnt + rcnt; }}int search(int x, int y, int k){ int l = -1000000000 - 1; int r = -l + 2; while (l < r){ int mid = (l + r) >> 1; int num = query(x, y+1, mid, 1, 1, n+1); if (k <= num) r = mid; else{ l = mid + 1; } } return l;}int main(){ while (cin >> n >> q) { for (int i = 1; i <= n; i++){ scanf("%d", a + i); } build(1, 1, n + 1); int li, ri, ki; for (int i = 0; i < q; i++){ scanf("%d%d%d", &li, &ri, &ki); printf("%d\n", search(li, ri, ki)); } } return 0;}