主席树 —— 区间第K大

模板题：POJ 2104

区间第K大模板：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//using pii = pair <ll,int>;
const int maxn = 1e5 + 10;
int n, m, a[maxn], root[maxn], tot;
int t[maxn*30], ls[maxn*30], rs[maxn*30];
vector <int> v;

int getid(int x){
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void update(int &rt, int pre, int l, int r, int pos){
	if(l>pos || r<pos) return;
	rt = ++tot;
	t[rt] = t[pre] + 1;
	ls[rt] = ls[pre], rs[rt] = rs[pre];
	if(l == r) return;
	int m = l + r >> 1;
	update(ls[rt],ls[pre],l,m,pos);
	update(rs[rt],rs[pre],m+1,r,pos);
}

int query(int rt, int pre, int l, int r, int k){
	if(l == r) return l;
	int m = l + r >> 1;
	int sum = t[ls[rt]] - t[ls[pre]];
	if(sum >= k) return query(ls[rt],ls[pre],l,m,k);
	return query(rs[rt],rs[pre],m+1,r,k-sum);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++)
		scanf("%d", a+i), v.push_back(a[i]);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i=1; i<=n; i++)
		update(root[i], root[i-1], 1, n, getid(a[i]));
	for(int i=1; i<=m; i++){
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		printf("%d\n", v[query(root[r], root[l-1], 1, n, k) - 1]);
	}
}