区间第K大板子(动态开点)
int n, m;
int root[N], idx;
struct node{
int l, r;
int cnt;
}tr[N * 40];
void pushup(int u){
tr[u].cnt = tr[tr[u].l].cnt + tr[tr[u].r].cnt;
}
void insert(int p, int &q, int l, int r, int x){
q = ++idx, tr[q] = tr[p];
if(l == r) tr[q].cnt++;
else{
int mid = l + r >> 1;
if(x <= mid) insert(tr[p].l, tr[q].l, l, mid, x);
else insert(tr[p].r, tr[q].r, mid + 1, r, x);
pushup(q);
}
}
int query(int p, int q, int l, int r, int k){
if(l == r) return l;
else{
int mid = l + r >> 1;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
if(cnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}
}
void solve(){
cin >> n >> m;
_for(i, 1, n){
int x;
cin >> x;
insert(root[i - 1], root[i], 0, INF, x);
}
while(m--){
int l, r, k;
cin >> l >> r >> k;
cout << query(root[l - 1], root[r], 0, INF, k) << endl;
}
}