http://poj.org/problem?id=2104
对权值进行建树（这个时候树的叶子是数组b的有序数列），然后二分查找原数列中每个数在有序数列中的位置（即第几小），对每一个前缀[1,i]建一棵树。用到前缀和的思想，区间第k小就可以直接查找T[r] - T[l-1]区间内第k小的数。如果对每一个前缀建一棵树，无疑会MLE，这个时候用到主席树。
主席树在我的理解：在更新的时候，只有一棵树中的一条路径有改变，这个时候我们只要修改改变的那条路径，而不是重新建一棵树。要做的是直接把上一个版本的线段树给现在的版本，然后对现在版本进行更新。
睡觉前不要打代码..做了一个晚上主席树的梦.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <iostream>
#include <stack>
using namespace std;
#define N 100010 /*
主席树
http://www.bilibili.com/video/av4619406/
http://www.cnblogs.com/Empress/p/4652449.html
题意:在一堆数里面有m个询问,每个询问求区间[l,r]里面的第k小的数是哪个.
要认识权值线段树：在以节点i为根的树中,[1,i]区间内包含的数的个数.
*/
struct node
{
int l, r, sum;//sum储存的就是权值
}tree[N*];
int root[N];//储存根节点
int a[N], b[N], tot; void update(int pre, int &now, int x, int l, int r)
{
tree[++tot] = tree[pre];//把上一个版本的线段树给现在的版本,然后对要修改的那条链进行更新
now = tot;
tree[now].sum++;//因为插入了新的数,所以要更新+1
if(l == r) return ;
int m = (l + r) >> ;
if(x <= m) update(tree[pre].l, tree[now].l, x, l, m);
else update(tree[pre].r, tree[now].r, x, m + , r);
} int query(int left, int right, int k, int l, int r)
{
if(l == r) return l;
int m = (l + r) >> ;
int sum = tree[tree[right].l].sum - tree[tree[left].l].sum;//如果左子树已经有k个数,那么答案就在左边
if(k <= sum) return query(tree[left].l, tree[right].l, k, l, m);
else return query(tree[left].r, tree[right].r, k - sum, m + , r);
} int main()
{
// int t;
// scanf("%d", &t);
// while(t--) {
int n, m;
scanf("%d%d", &n, &m);
tot = ;
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + , b + + n);
int cnt = unique(b + , b + + n) - b - ;
for(int i = ; i <= n; i++) {
a[i] = lower_bound(b + , b + + cnt, a[i]) - b; //二分找到a[i]的位置
// printf("QQQQQ\n");
update(root[i-], root[i], a[i], , cnt); //root[i-1]表示上一个版本的线段树
}
for(int i = ; i <= m; i++) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
int ans = query(root[l-], root[r], k, , cnt); //ans是第k个数的位置
printf("%d\n", b[ans]); //因为询问的是哪个数,所以要b[ans]
}
// }
return ;
}