可持久化线段树

区间第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;
	}
}