题目链接：https://cn.vjudge.net/contest/284294#problem/B
题目大意：查询区间内有多少个不相同的数。
具体思路：主席树的做法，主席树的基础做法是查询区间第k大或者第k小的，但是这个地方查询的是区间内不同的数的个数，我们就按照下标建立主席树，对于区间[l,r]，我们存储的是区间[l,r]中有多少个不同的数，对于当前的数，如果没有出现过，我们就在第i个位置给他加上，如果已经出现过，我们在建立下一棵主席树的时候，先将之前的这个数的下标对应的值减去1.探后再在第i个位置加上这个1，这样的话，可以实现题目中的操作了。
AC代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
# define ll long long
const int maxn = 1e5+;
struct node
{
int sum;
int l,r;
} tree[maxn*];
int sto[maxn],root[maxn];
vector<int>q;
int tot;
void init()
{
tot=;
root[]=;
}
int get_id(int t)
{
return lower_bound(q.begin(),q.end(),t)-q.begin()+;
}
int add(int pre)
{
int t=++tot;
tree[t].sum=tree[pre].sum+;
tree[t].l=tree[pre].l;
tree[t].r=tree[pre].r;
return t;
}
void update(int &o,int pre,int l,int r,int pos)
{
o=add(pre);
if(l==r)return ;
int m=(l+r)>>;
if(pos<=m)update(tree[o].l,tree[o].l,l,m,pos);
else update(tree[o].r,tree[o].r,m+,r,pos);
}
int query(int st,int ed,int l,int r,int k){
if(l==r)return r;
int sum=tree[tree[ed].l].sum-tree[tree[st].l].sum;
int m=(l+r)>>;
if(k<=sum)return query(tree[st].l,tree[ed].l,l,m,k);
else return query(tree[st].r,tree[ed].r,m+,r,k-sum);
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
init();
for(int i=; i<=n; i++)
{
scanf("%d",&sto[i]);
q.push_back(sto[i]);
}
sort(q.begin(),q.end());
q.erase(unique(q.begin(),q.end()),q.end());
int num=q.size();
for(int i=; i<=n; i++)
{
update(root[i],root[i-],,num,get_id(sto[i]));
}
int t1,t2,k;
while(m--){
scanf("%d %d %d",&t1,&t2,&k);
printf("%d\n",q[query(root[t1-],root[t2],,num,k)-]);
}
}
return ;
}