学习报告：主席树真的nb，如果朴素做要开n个线段树，内存爆炸，优化的方式，每次插入一个数，并不是整个权值线段树都改变了，只是改变logn个节点，我们只需要多开logn个节点就OK，用root数组记录历史个线段树版本，询问区间，可以做相减，询问第k小值，与左树的所有节点sum作比较，如果小就在左边，否则在右边，在右边的时候注意是k-sum，由于值域太大，可以使用离散化，获得每个数的排名，可以把值域缩小到n。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=200010;
struct node{
	int l;
	int r;
	int sum;
}tr[N*40];
int root[N];
int w[N],cnt;
vector<int>v;
int getid(int x)
{
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void modify(int l,int r,int pre,int &now,int k)
{
	tr[++cnt]=tr[pre];
	now=cnt;
	tr[now].sum++;
	if(l==r)	return ;
	int mid=l+r>>1;
	if(k<=mid)	modify(l,mid,tr[pre].l,tr[now].l,k);
	else		modify(mid+1,r,tr[pre].r,tr[now].r,k);
}
int query(int l,int r,int L,int R,int k)
{
	if(l==r)
	return l;
	int sum=tr[tr[R].l].sum-tr[tr[L].l].sum;
	int mid=l+r>>1;
	if(k<=sum)	return query(l,mid,tr[L].l,tr[R].l,k);
	else		return query(mid+1,r,tr[L].r,tr[R].r,k-sum);
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
	cin>>w[i];
	v.push_back(w[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++)
	{
		modify(1,n,root[i-1],root[i],getid(w[i]));
	}
	while(m--)
	{
		int l,r,k;
		cin>>l>>r>>k;
		cout<<v[query(1,n,root[l-1],root[r],k)-1]<<endl;
	}
    return 0;
}