题目
思路
主席树大家一定都有所了解吧，这一题就是主席树的模板啊！！
静态区间第K小，不就说明了这题可以用主席树吗？主席树中动态开点就不多说了吧
还有就是没看这n个数的范围这么大吗？一定要用离散化
算法
想必大家都会一点点主席树吧，那蒟蒻我就不再多说了，实在不行可以看看上面大佬的题解，或是找几篇博客看看，还可以找几个视频看看。
代码
不必多说了吧，代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using namespace std;
const int maxn=500001;
struct node{
int l,r,sum;
}T[maxn*20];//这是保存树的结构体
struct zz{
int x,id;
}a[maxn];//离散化时要用
int n,m,b[maxn],cnt,root[maxn];
bool cmp(zz a,zz b){return a.x<b.x;}
void update(int x,int &rt,int l,int r){//建树
//注意，这里的rt，也就是这棵树的根是会变的
T[++cnt]=T[rt]; rt=cnt; T[rt].sum++;//先与上一个树一样，有改变的地方再新建点
if(l==r) return;
int mid=(l+r)>>1;//这里就和线段树的操作一样
if(x<=mid) update(x,T[rt].l,l,mid);
else update(x,T[rt].r,mid+1,r);
}
int ask(int rt1,int rt2,int x,int l,int r){//查询
int d=T[T[rt2].l].sum-T[T[rt1].l].sum;
//前缀和思想，也可以拆开来一颗树一棵树的写，这里我是将它放一起做了
if(l==r) return l;
int mid=(l+r)>>1;
if(x<=d) return ask(T[rt1].l,T[rt2].l,x,l,mid);
//如果这区间左半边的数的数量比x大，那第x小的数一定在左半边。
else return ask(T[rt1].r,T[rt2].r,x-d,mid+1,r);
//不然就在右半边找第x-d大的数
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].x);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);//先排序一遍，从小到大
for(int i=1;i<=n;i++) b[a[i].id]=i;//离散化关键点
for(int i=1;i<=n;i++){
root[i]=root[i-1];
update(b[i],root[i],1,n);
}//建树
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
printf("%d\n",a[ask(root[x-1],root[y],z,1,n)].x);//找区间x到y之间第K小的数
//转化成前缀和，主席树基本操作
}
return 0;
}