基准时间限制：1 秒 空间限制：131072 KB 分值: 160 难度：6级算法题
一个长度为N的整数序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，第K大的数是多少。
例如: 1 7 6 3 1。i = 1, j = 3，k = 2，对应的数为7 6 3，第2大的数为6。
Input
第1行：1个数N，表示序列的长度。(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应序列中的元素。(0 <= S[i] <= 10^9)
第N + 2行：1个数Q，表示查询的数量。(2 <= Q <= 50000)
第N + 3 - N + Q + 2行：每行3个数，对应查询的起始编号i和结束编号j，以及k。(0 <= i <= j <= N - 1,1 <= k <= j - i + 1)
Output
共Q行，对应每一个查询区间中第K大的数。
Input示例
5
1
7
6
3
1
3
0 1 1
1 3 2
3 4 2
Output示例
7
6
1 思路：
可持久化线段树入门题。离散化处理下就好了
其实可持久化线段树跟之前写过的线段树动态开点是差不多的，都是为了维护状态，需要开很多棵线段树来维护。
可持久化线段树维护的是每一次修改后的状态。比如这道题我们就可以利用他的能够查询历史版本的特性来解决 ps：之前有点错误，改正了一遍 实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 2e6+;
int idx; //记录目前一共建过多少节点
int sum[M],ls[M],rs[M]; //区间和，左儿子，右儿子
int rt[M]; //每次修改对应的根节点编号
int a[M],ans[M],lst[M],cnt,num[M],n,m; struct node{
int id,l,r,x;
bool operator < (const node &b) const {
return r < b.r;
}
}q[M]; void build(int &k,int l,int r){
//k传的是地址，这样在一层函数中修改k就可以直接修改上一层的lson和rson了
k = ++idx; //为新节点标号
if(l == r) return ; //一定要在创建新节点之后再return
int m = (l + r) >> ;
build(ls[k],l,m);
build(rs[k],m+,r);
} void change(int old,int &k,int l,int r,int p,int x){
k = ++idx; //修改的时候要创建新点
ls[k] = ls[old]; rs[k] = rs[old];
sum[k] = sum[old] + x; //先把原来节点的信息复制过来，顺便修改区间和
if(l == r) return ; //先建点后return
int m = (l + r) >> ;
if(p <= m) change(ls[old],ls[k],l,m,p,x);
else change(rs[old],rs[k],m+,r,p,x);
} int query(int k,int old,int l,int r,int x){
if(l == r) return l;
int m = (l + r) >> ;
int ret = sum[rs[k]] - sum[rs[old]];
if(ret >= x)
return query(rs[k],rs[old],m+,r,x);
else
return query(ls[k],ls[old],l,m,x-ret);
} int find(int x){
return lower_bound(num+,num + cnt + , x) - num;
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
cin>>n;
for(int i = ;i <= n;i ++){
cin>>lst[i];a[i] = lst[i];
}
sort(lst+,lst+n+);
for(int i = ;i <= n;i ++){
if(i == ||lst[i] != lst[i-])
num[++cnt] = lst[i];
}
build(rt[],,cnt);
cin>>m;
for(int i = ;i <= m;i ++){
q[i].id = i;
cin>>q[i].l; q[i].l ++;
cin>>q[i].r; q[i].r ++;
cin>>q[i].x;
}
sort(q+,q+m+);
for(int i = ,j = ;i <= n;i ++){
change(rt[i-],rt[i],,cnt,find(a[i]),);
while(q[j].r == i){
ans[q[j].id] = query(rt[i],rt[q[j].l-],,cnt,q[j].x);
j++;
}
}
for(int i = ;i <= m;i ++){
printf("%d\n",num[ans[i]]);
}
return ;
}