一.查询区间[l,r]第k大

离散化版本

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
struct tree{
    int ch[2];
    int s;
}tr[N<<5];
int idx=0;
int root[N];
vector<int>v;
int getid(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void build(int &x,int l,int r){
    x=++idx;
    if(l==r) return;
    int m=(l+r)>>1;
    build(tr[x].ch[0],l,m);
    build(tr[x].ch[1],m+1,r);
}
void modify(int x,int &y,int l,int r,int v){
    y=++idx;
    tr[y]=tr[x];
    tr[y].s++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(v<=m) modify(tr[x].ch[0],tr[y].ch[0],l,m,v);
    else modify(tr[x].ch[1],tr[y].ch[1],m+1,r,v);
}
int query(int x,int y,int l,int r,int val){
    if(l==r) return l;
    int m=(l+r)>>1;
    int s=tr[tr[y].ch[0]].s-tr[tr[x].ch[0]].s;
    if(val<=s) return query(tr[x].ch[0],tr[y].ch[0],l,m,val);
    else return query(tr[x].ch[1],tr[y].ch[1],m+1,r,val-s); 
}
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int vn = v.size();
    build(root[0], 1, vn);
    for (int i = 1; i <= n; i++)
        modify(root[i-1], root[i], 1, vn, getid(a[i]));
    
    for (int i = 1; i <= m; i++){
        int l, r, k;
        cin >> l >> r >> k;
        int id = query(root[l-1], root[r], 1, vn, k) - 1;
        cout << v[id] << endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

二.查询区间[l,r]中有多少个数字小于a[k]

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
struct tree{
    int ch[2];
    int s;
}tr[N>>5];
int idx=0;
int root[N];
void build(int &x,int l,int r){
    x=++idx;
    if(l==r) return;
    int m=(l+r)>>1;
    build(tr[x].ch[0],l,m);
    build(tr[x].ch[1],m+1,r);
}
void modify(int x,int &y,int l,int r,int v){
    y=++idx;
    tr[y]=tr[x];
    tr[y].s++;
    if(l==r) return;
    int m=(l+r)>>1;
    if(v<=m) modify(tr[x].ch[0],tr[y].ch[0],l,m,v);
    else modify(tr[x].ch[1],tr[y].ch[1],m+1,r,v);
}
int query(int x,int y,int l,int r,int val){
    if(r<=val) return tr[y].s-tr[x].s;
    int m=l+r>>1;
    if(val<=m){
        return query(tr[x].ch[0],tr[y].ch[0],l,m,val);
    }
    else{
        return query(tr[x].ch[0],tr[y].ch[0],l,m,val)+query(tr[x].ch[1],tr[y].ch[1],m+1,r,val);
    }
}
void solve(){
    int n,m;
    cin>>n>>m;
    build(root[0],1,n);
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        modify(root[i-1],root[i],1,n,a[i]);
    }
    for(int i=1;i<=m;i++){
        int num,l,r;
        cin>>l>>r>>num;
        cout<<query(root[l-1],root[r],1,n,a[num])+l-1<<endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}