像平衡树一样，只不过左子树表示的是[l,mid]的所有值，右子树表示的是[mid+1,r]的所有值，一般是维护一个cnt就可以类似在平衡树上面二分出第k小，也可以求出第k小的值在主席树中是哪个元素。当然根据你的想象力，所有只跟左子树或者右子树单侧相关的都可以找。

#include
    
     #define mid ((l+r)>>1)using namespace std;typedef long long ll;const int MAXN = 200000 + 5;int T[MAXN], tcnt;int cnt[MAXN << 5], L[MAXN << 5], R[MAXN << 5];ll sum[MAXN << 5];int a[MAXN], rnk[MAXN], val[MAXN];inline int build(int l, int r) {    int rt = ++tcnt;    cnt[rt] = 0;    sum[rt] = 0;    if(l < r) {        L[rt] = build(l, mid);        R[rt] = build(mid + 1, r);    }    return rt;}inline int update(int pre, int l, int r, int x, int val) {    int rt = ++tcnt;    R[rt] = R[pre];    L[rt] = L[pre];    cnt[rt] = cnt[pre] + 1;    //这里传入的是离散化后的x，那应该加上x对应的原值val    sum[rt] = sum[pre] + val;    if(l < r) {        if(x <= mid)            L[rt] = update(L[pre], l, mid, x, val);        else            R[rt] = update(R[pre], mid + 1, r, x, val);    }    return rt;}//查询[u-1,v]中排名为rk的数inline int query0(int u, int v, int l, int r, int rk) {    //比整个区间的数都多，那是INF    if(rk>cnt[v]-cnt[u])        exit(-1);    //直到进入一个叶子    while(l < r) {        int tmp=cnt[L[v]] - cnt[L[u]];        if(tmp < rk) {            //整个左子树加起来的数量都是
     
      val[r])        return cnt[v]-cnt[u]+1;    //直到进入一个叶子    while(l < r) {        if(val[mid] < va) {            //左子树的最大值比这个小，进入右子树            u = R[u], v = R[v], l = mid + 1;        } else{            u = L[u], v = L[v], r = mid;        }    }    //最后到达了一个叶子    return l;}//查询[u-1,v]中排名不超过rk的数的个数inline int query2(int u, int v, int l, int r, int rk) {    int res = 0;    while(l < r && rk < r) {        if(mid <= rk) {            //整个左子树都是<=rk            res += cnt[L[v]] - cnt[L[u]];            u = R[u], v = R[v], l = mid + 1;        } else            u = L[u], v = L[v], r = mid;    }    if(rk >= l)        res += cnt[v] - cnt[u];    return res ;}//查询[u-1,v]中排名不超过rk的数的和inline ll query3(int u, int v, int l, int r, int rk) {    //上面的cnt变成sum}//查询[u-1,v]中值不超过va的数的个数inline int query4(int u, int v, int l, int r, int va) {    int res = 0;    while(l < r && va < val[r]) {        if(val[mid] <= va) {            //整个左子树都是<=v            res += cnt[L[v]] - cnt[L[u]];            u = R[u], v = R[v], l = mid + 1;        } else            u = L[u], v = L[v], r = mid;    }    if(va >= val[l])        res += cnt[v] - cnt[u];    return res ;}//查询[u-1,v]中值不超过va的数的和inline ll query5(int u, int v, int l, int r, int va) {    //上面的cnt变成sum}int main() {#ifdef Yinku    freopen("Yinku.in", "r", stdin);#endif // Yinku    int n, q;    while(~scanf("%d%d", &n, &q)) {        for(int i = 1; i <= n; i ++) {            scanf("%d", &a[i]);            rnk[i] = a[i];        }        sort(rnk + 1, rnk + 1 + n);        int cb = unique(rnk + 1, rnk + 1 + n) - rnk - 1;        tcnt = 0;        T[0] = build(1, cb);        for(int i = 1; i <= n; i ++) {            int rk = lower_bound(rnk + 1, rnk + 1 + cb, a[i]) - rnk;            val[rk] = a[i];            T[i] = update(T[i - 1], 1, cb, rk, val[rk]);        }        while(q--) {            int l, r, k;            scanf("%d%d%d", &l, &r, &k);            printf("%d\n", query0(T[l - 1], T[r], 1, cb, k));        }    }    return 0;}