感谢$Refun$大爷的耐心讲解Orz
首先主席树维护的是什么东西呢？
我们在每个节点都建一棵线段树，$i$节点的线段树维护的是$1$到$i$这段区间的值域里的每个数的出现次数（有点像前缀和的样子）
既然要搞值域，我们把给定的序列离散化一下
举个栗子：给定序列：1 5 4 7 2 3 3
排序后去重就是：1 2 3 4 5 7
重新编号：1 2 3 4 5 6
首先是节点$1$，ta维护的是$[1,1]$这段区间里$1$到$6$（编号）每个数出现次数
显然这棵线段树叶子节点就是：1 0 0 0 0 0
再是节点$2$，ta维护的是$[1,2]$这段区间里$1$到$6$（编号）每个数出现次数（第二个节点是$5$，编号也是$5$）
这棵线段树叶子节点就是：1 0 0 0 1 0
以此类推
这么搞是可行的，查询区间$k$大值直接二分查找就行了
但是一般数据范围都是$1e5$的，每个节点建一棵线段树，就要开$1e5\times 1e5\times 4$的空间差不多是160个G？，炸了……
可以发现，第$i$棵线段树跟第$i-1$棵线段树是有联系的
只是点$i$对应的值出现次数$+1$了而已
所以我们只需要将第$i$棵线段树没有修改的部分跟第$i-1$棵共用就行了
现在问题其实已经解决完了，再捋一遍：
序列里每个节点建一棵线段树，维护$1$到$i$区间值域每个值的出现次数（注意是每个值）
我们加入一个节点的线段树可以与前面的线段树共用大部分节点（具体实现可以看代码）
加入这个节点的值，可以lower_bound一下去重数组，找到这个节点值应该在的位置然后单点修改
然后求区间值相当于一个前缀和求区间值的过程，设区间左右端点为$l$和$r$
在第$l-1$棵线段树和第r棵线段树上同步操作
这两棵线段树（注意线段树的维护区间都是整个值域）节点维护的值相减，然后根据比较减值和要求的值的大小决定向左走还是向右走（类似平衡树找k大值过程）
直到找到叶子节点
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define mid (l+r>>1)
using namespace std;
const int MAX=2e5+1;
struct p{
int x,l,r;
}s[MAX<<5];
int n,m,tot;
int a[MAX],b[MAX],rt[MAX];
int read()
{
int x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int build(int l,int r)
{
int k=++tot;
if(l==r) return k;
s[k].l=build(l,mid);
s[k].r=build(mid+1,r);
return k;
}
int change(int pre,int l,int r,int x)
{
int k=++tot;
s[k].l=s[pre].l,s[k].r=s[pre].r;
s[k].x=s[pre].x+1;
if(l==r) return k;
if(x<=mid) s[k].l=change(s[pre].l,l,mid,x);
else s[k].r=change(s[pre].r,mid+1,r,x);
return k;
}
int ask(int L,int R,int l,int r,int k)
{
if(l==r) return l;
int x=s[s[R].l].x-s[s[L].l].x;
if(x>=k) return ask(s[L].l,s[R].l,l,mid,k);
else return ask(s[L].r,s[R].r,mid+1,r,k-x);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=b[i]=read();
sort(a+1,a+1+n);
int L=unique(a+1,a+1+n)-a-1;
rt[0]=build(1,L);
for(int i=1;i<=n;i++)
{
int t=lower_bound(a+1,a+1+L,b[i])-a;
rt[i]=change(rt[i-1],1,L,t);
}
for(int i=1;i<=m;i++)
{
int l=read(),r=read(),k=read();
printf("%d\n",a[ask(rt[l-1],rt[r],1,L,k)]);
}
return 0;
}
