<—点个赞吧QwQ

宣传一下[算法提高课整理]

给定长度为 $N$ 的整数序列 $A$，下标为 $1 \sim N$。

现在要执行 $M$ 次操作，其中第 $i$ 次操作为给出三个整数 $l_i,r_i,k_i$，求 $A[l_i],A[l_i+1],…,A[r_i]$ (即 $A$ 的下标区间 $[l_i,r_i]$)中第 $k_i$ 小的数是多少。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，表示整数序列 $A$。

接下来 $M$ 行，每行包含三个整数 $l_i,r_i,k_i$，用以描述第 $i$ 次操作。

输出格式

对于每次操作输出一个结果，表示在该次操作中，第 $k$ 小的数的数值。

每个结果占一行。

数据范围

$N \le 10^5, M \le 10^4,|A[i]| \le 10^9$

输入样例：

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

输出样例：

5
6
3

思路

可持久化线段树的博客
这里我们要用的数据结构是可持久化权值线段树，也就是主席树，注意它存储的是数的值域。
我们把$n$个数分$n$次插入，第$i$个根$root_i$，表示前$i$个数的，但是我们要求任意区间的第$k$小数，所以我们可以用第$r$棵树的每一个数减去第$l-1$棵树的每一个数，得到的结果就是$[l,r]$区间里的树，再在树上进行二分即可。

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,t;
int a[N],b[N];
struct segment_tree_node {
    int lc,rc;
    int sum;
}tr[4 * N + N * 17];
int idx;
int root[N];
void push_up (int u) {
    tr[u].sum = tr[tr[u].lc].sum + tr[tr[u].rc].sum;
}
int build (int l,int r) {
    int u = ++idx;
    if (l == r) return u;
    int mid = l + r >> 1;
    tr[u] = {build (l,mid),build (mid + 1,r)};
    return u;
}
int insert (int v,int l,int r,int x) {
    int u = ++idx;
    tr[u] = tr[v];
    if (l == r) {
        tr[u].sum++;
        return u;
    }
    int mid = l + r >> 1;
    if (x <= mid) tr[u].lc = insert (tr[u].lc,l,mid,x);
    else tr[u].rc = insert (tr[u].rc,mid + 1,r,x);
    push_up (u);
    return u;
}
int query (int u,int v,int l,int r,int k) {
    if (l == r) return l;
    int x = tr[tr[u].lc].sum - tr[tr[v].lc].sum,mid = l + r >> 1;;
    if (k <= x) return query (tr[u].lc,tr[v].lc,l,mid,k);
    return query (tr[u].rc,tr[v].rc,mid + 1,r,k - x);
}
int main () {
    cin >> n >> t;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort (b + 1,b + 1 + n);
    int m = unique (b + 1,b + 1 + n) - b - 1;
    root[0] = build (1,m);
    for (int i = 1;i <= n;i++) root[i] = insert (root[i - 1],1,m,lower_bound (b + 1,b + 1 + m,a[i]) - b);
    while (t--) {
        int l,r,k;
        cin >> l >> r >> k;
        cout << b[query (root[r],root[l - 1],1,m,k)] << endl;
    }
    return 0;
}