POJ2104 K-th Number Range Tree
又是区间第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<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#define maxn 100000
using namespace std;
vector<int> 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
", search(li, ri, ki));
}
}
return 0;
}