学步园

注意：这题题意写错了，不是区间第k大，而是区间第k小， WA了一地，看了discuss才知道，坑啊

参考了clj的论文《可持久化数据结构研究》，具体做法论文里很明确。

其实思想还是建多颗线段树，只是把这些线段树数据不相同的部分另外建了一些节点。

对于m个询问，每次要建log(n)的节点，需要 n*2+mlog(n)的内存，这题写得不好数组就开不下了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l, m, ls[rt]
#define rson m+1, r, rs[rt]
#define Mid int m = l+r>>1
const int maxn = 100005;
int ls[maxn*20], rs[maxn*20], sum[maxn*20], tot;
int root[maxn];
void build(int l, int r, int &rt) {
	rt = ++tot;
	sum[rt] = 0;
	if(l == r) return;
	Mid;
	build(lson);
	build(rson);
}

void update(int o, int p, int v, int l, int r, int &rt) {
	rt = ++tot;
	sum[rt] = sum[o] + v;
	ls[rt] = ls[o];
	rs[rt] = rs[o];
	if(l == r) return;
	Mid;
	if(p <= m) update(ls[o], p, v, lson);
	else update(rs[o], p, v, rson);
}

int query(int o, int k, int l, int r, int rt) {   //o-->rt 第k小的数
	if(l == r) return l;
	Mid;
	int res = sum[ls[rt]] - sum[ls[o]];
	if(k <= res) return query(ls[o], k, lson);
	else return query(rs[o], k-res, rson);
}
int a[maxn], b[maxn];
int main() {
	int i, j, cas;
	int n, m;
	scanf("%d", &cas);
	while(cas--) {
		scanf("%d%d", &n, &m);
		for(i = 0; i < n; i++) {
			scanf("%d", &a[i]);
			b[i] = a[i];
		}
		sort(b, b+n);
		int sz = unique(b, b+n)-b;
		tot = 0;
		build(1, sz, root[0]);
		for(i = 0; i < n; i++) {
			j = lower_bound(b, b+sz, a[i])-b+1;
			update(root[i], j, 1, 1, sz, root[i+1]);
		}
		while(m--) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			printf("%d\n", b[query(root[x-1], z, 1, sz, root[y])-1]);
		}
	}
}