RT，悬赏2关

代码中写了许多的注释方便理解，感谢大佬指点一下QAQ

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define For(i , j , k) for(int i = j; i <= k; i ++)
#define MaxN 200005

struct Node{                            //节点
	int l , r;//该区间的左右端点
	int cnt;  //该区间的数的数量
}tr[MaxN * 22];
int a[MaxN] , b[MaxN];                  //原数组与去重后的数组
int root[MaxN] , len = 0 , lenb;        //记录根节点数组（每个版本的根节点），结点数量，去重后数组长度
int n , m;
//建树过程 注意：这里建的是空树，作为最开始的情况（版本0）
void Build(int op , int l , int r)
{
	int mid = (l + r) >> 1;
	tr[ ++ len ].l = l;                 //初始化
	tr[ len ].r = r;
	tr[ len ].cnt = 0;
	if(l == r) return ;
	//二分建树
	Build(op * 2 , l , mid);
	Build(op * 2 + 1 , mid + 1 , r);
}
//插入操作：对于新加入的数，只对于包括它的区间节点进行复制新节点操作，省去了空间
//参数：被复制的编号；新节点的编号；范围左、右边界；插入的数
void insert(int x , int &y , int l , int r , int val)
{                                       //插入操作（建立新版本）
	int mid = (l + r) >> 1;
	y = ++len;                          //复制一个与先前相同的节点，作为新版本
	tr[y] = tr[x];
	tr[y].cnt ++;                       //此时该区间的数的数量+1
	if(l == r) return ;                 //递归到原区间就返回
	//二分查找下一个需要操作的区间
	if(val <= mid)                      
		insert(tr[x].l , tr[y].l , l , mid , val);
	else
		insert(tr[x].r , tr[y].r , mid + 1 , r , val);
}
//查询操作：查询[l,r]的信息=[1,r]的信息-[1,l-1]的信息，再通过[l,r]中两个子儿子的数量来二分查找
//参数：第l-1个版本的编号；第r个版本的编号；范围左右边界；查询第k小
int query(int x , int y , int l , int r , int k)
{
	if(l == r) return l;
	
	int mid = (l + r) >> 1;
	int sum = tr[y].cnt - tr[x].cnt;        //算出[l,r]区间的数个数
	if(k <= sum)                            //判断第k小在哪个区间
		return query(tr[x].l , tr[y].l , l , mid , k);
	else
		return query(tr[x].r , tr[y].r , mid + 1 , r , k - sum);
}
//查询离散化后数的新下标：二分查找
int getid(int x) {return lower_bound(b + 1 , b + lenb + 1 , x) - b;}

int main()
{
	cin >> n >> m;
	Build(1 , 1 , n);
	For(i , 1 , n)          //输入数组
	{
		cin >> a[i];
		b[i] = a[i];        //b数组查询备用
	}
	//去重三部曲
	sort(b + 1 , b + 1 + n);                    //排序
	lenb = unique(b + 1 , b + 1 + n) - b - 1;   //去重
    //获取下标：getid()
	For(i , 1 , n)                              //对每个数进行插入操作
		insert(root[i - 1] , root[i] , 1 , lenb , getid(a[i]));
	
	//查询操作
    while(m --) 
	{
		int x , y , z , ans;
		cin >> x >> y >> z;
		ans = query(root[x - 1] , root[y] , 1 , lenb , z);
		cout << b[ans] << endl;
	}

    system("pause");
	return 0;
}