主席树的板子

#include
using namespace std;
using VI = vector<int>;
using ll = long long;
using PII = pair;
const ll mod = 998244353;
const int N = 2e5 + 10;
int n,m;
int a[N];
int b[N];
struct Segment{
    int ls,rs,val;
};
struct PST{
    Segment t[N << 5];
    int idx = 0;
    int root[N << 5];
    int build(int p ,int l ,int r){
        p = idx++;
        if(l == r) return p;
        int mid = (l + r) >> 1;
        t[p].ls = build(t[p].ls , l , mid);
        t[p].rs = build(t[p].rs , mid + 1 , r);
        return p;
    }
    int copy(int p){
        idx++;
        t[idx] = t[p];
        t[idx].val++;
        return idx;
    }
 
    int change(int p , int l , int r, int pos){
 
        p = copy(p);
        if(l == r) return p;
        int mid = (l + r) >> 1;
        if(pos <= mid) t[p].ls = change(t[p].ls , l , mid , pos);
        else t[p].rs = change(t[p].rs , mid + 1 , r , pos);
        return p;
    }
    int query(int p , int q , int l , int r ,int k){ //( p ,  q ]区间的的k
        if(l == r) return b[l];
        int mid = (l + r) >> 1;
        int sum = t[t[q].ls].val - t[t[p].ls].val;
        if(k <= sum) return query(t[p].ls , t[q].ls , l , mid , k);
        else return query(t[p].rs , t[q].rs , mid + 1, r , k - sum);
    }
}s;
 
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i++) cin>>a[i],b[i] = a[i];
    sort(b + 1 , b + 1 + n);
    int tot = unique(b + 1 , b + 1 + n) - b - 1;
    s.root[0] = s.build(s.root[0] , 1 , tot);
    for(int i = 1 ; i <= n ; i++){
        a[i] = lower_bound(b + 1 , b + 1 + tot , a[i]) - b;
        s.root[i] = s.change(s.root[i - 1] , 1 , tot , a[i]);
    }
    for(int i = 1 ; i <= m ; i++){
        int l,r,k;
        cin>>l>>r>>k;
        cout<query( s.root[l - 1] , s.root[r] , 1 , tot , k)<<'\n';
    }
 
 
}

大致就是利用前缀和的思想去寻找区间第k大

先思考全局查询的时候，就是看第k大是在左边的区间还是右边的区间‘

然后二分着找

现在改成[l , r] 上的查询的就通过维护1-i的线段树实现