题目：https://www.luogu.org/problemnew/show/P3834
无法忍受了，我要写主席树！
解决区间第 k 大查询问题，可以用主席树，像前缀和一样建立 n 棵前缀区间的权值线段树；
然后 n 棵线段树可以共用一些节点；
线段树的 sum 可以相减，利用这个查询即可；
什么嘛，主席树也没我想得那么难(蛮简单的)！
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=2e5+;
int n,m,q,t[maxn],ls[maxn<<],rs[maxn<<],sum[maxn<<],cnt,a[maxn],b[maxn];
//注意数组范围，每次新增log(m)个点
int build(int l,int r)
{
int rt=++cnt,mid=((l+r)>>);
sum[rt]=;
if(l<r){build(l,mid); build(mid+,r);}
return rt;
}
int update(int pre,int l,int r,int x)
{
int rt=++cnt,mid=((l+r)>>);
ls[rt]=ls[pre]; rs[rt]=rs[pre]; sum[rt]=sum[pre]+;
if(l<r)
{
if(x<=mid)ls[rt]=update(ls[pre],l,mid,x);
else rs[rt]=update(rs[pre],mid+,r,x);
}
return rt;
}
int query(int u,int v,int l,int r,int k)
{
if(l>=r)return l;
int mid=((l+r)>>);
int x=sum[ls[v]]-sum[ls[u]];
if(x>=k)return query(ls[u],ls[v],l,mid,k);
else return query(rs[u],rs[v],mid+,r,k-x);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+,b+n+);
m=unique(b+,b+n+)-b-;
t[]=build(,m);
for(int i=;i<=n;i++)
{
int tmp=lower_bound(b+,b+m+,a[i])-b;
t[i]=update(t[i-],,m,tmp);
}
for(int i=,l,r,x;i<=q;i++)
{
scanf("%d%d%d",&l,&r,&x);
int tmp=query(t[l-],t[r],,m,x);
printf("%d\n",b[tmp]);
}
return ;
}