8.23复学记

#include <algorithm> 
#include <cstdio>
#include <iostream>

const int N = 2e5 + 3;

int n, m, a[N], p[N], T[N], s, cnt;//T树根编号 
int sum[N << 5], L[N << 5], R[N << 5];//L左孩子编号，sum包含元素个数 

int build(int l, int r) {
	int rt = ++cnt;
	if (l < r) {
		int mid = (l + r) >> 1;
		L[rt] = build(l, mid);
		R[rt] = build(mid + 1, r);
	}
	return rt;
}//build一棵空树 

int update(int pre, int l, int r, int x) {
	int rt = ++cnt;//新建节点 
	L[rt] = L[pre], R[rt] = R[pre], sum[rt] = sum[pre] + 1;//左右儿子继承之前版本，元素个数在前版本基础上+1 
	if (l < r) {
		int mid = (l + r) >> 1;
		if (x <= mid) L[rt] = update(L[pre], l, mid, x);
		else R[rt] = update(R[pre], mid + 1, r, x);
	}
	return rt;
}

int query(int u, int v, int l, int r, int k) {
	if (l >= r) return l;
	int x = sum[L[v]] - sum[L[u]], mid = (l + r) >> 1;
	if (x >= k) return query(L[u], L[v], l, mid, k);
	else return query(R[u], R[v], mid + 1, r, k - x);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		p[i] = a[i];
	}
	std::sort(p + 1, p + n + 1);
	s = std::unique(p + 1, p + n + 1) - p - 1;
	T[0] = build(1, s);
	for (int i = 1; i <= n; ++i) {
		T[i] = update(T[i - 1], 1, s, std::lower_bound(p + 1, p + 1 + s, a[i]) - p);
	}
	for (int i = 1, l, r, k; i <= m; ++i) {
		scanf("%d %d %d", &l, &r, &k);
		printf("%d\n", p[query(T[l - 1], T[r], 1, s, k)]);
	}
	return 0;
}