欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【模版】静态区间第k小 (可持久化线段树)

程序员文章站 2024-03-04 12:08:47
...
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

struct Seg{int l, r, sum;}T[maxn<<5];
int cnt = 0;
void update(int &now, int old, int l, int r, int pos){
    now = ++cnt; T[now] = T[old]; T[now].sum ++;
    if(l == r) return ;
    int mid = l+r >> 1;
    if(pos <= mid) update(T[now].l, T[old].l, l, mid, pos);
    else update(T[now].r, T[old].r, mid+1, r, pos);
}
int query(int L, int R, int l, int r, int k){
    if(l == r) return l;
    int mid = l+r >> 1;
    int res = T[T[R].l].sum - T[T[L].l].sum;
    if(k <= res) return query(T[L].l, T[R].l, l, mid, k);
    else return query(T[L].r, T[R].r, mid+1, r, k-res);
}
int n, m, l, r, k, rt[maxn], a[maxn];
int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i], update(rt[i], rt[i-1], 1, n, a[i]);
    while(m--){
        cin >> l >> r >> k;
        cout << query(rt[l-1], rt[r], 1, n, k) << endl;
    }
}