【模版】静态区间第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;
}
}
上一篇: 可持久化数组