【模板】区间第k小 / 可持久化线段树 2（主席树）

题目链接：ybt金牌导航4-6-1 / luogu P3834

题目大意

对于一个数组，求一个区间第 k 小的值。

思路

这里假设已经会做可持续化线段树1。

那你想想怎么弄。
首先这道题数很大，但是真实个数又很小，而且只是比较大小关系。那我们可以把它离散化。
那离散化有什么用呢？可以放进数组里，显示这个数有多少个。

那我们可以用线段树存，存某个数到某个数之间出现了多少次。
但是两边都不确定不好弄，我们就确定左边是最左边。

那你就一开始树上都是 $0$，因为你一个数都没有。
然后你每次插一个数，就像弄可持续化线段树一样弄。

然后你考虑怎么查询。
你可以用前缀和的方法，两个树各个位置相减，就得到了区间对应的树。当然这个树不用构造出来，你只要走的时候减一下就可以。

然后你线段树记录它子树的值的和，就可以找到第 k 小了。

代码

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

using namespace std;

struct node {
	int x, num, xx;
}a[200001];
struct Tree {
	int l, r, x;
}tree[200001 << 5];
int n, m, num, dy[200001];
int root[200001], tot, L, R, K;

bool cmp(node x, node y) {
	return x.x < y.x;
}

bool cmp_b(node x, node y) {
	return x.num < y.num;
}

int clone(int now) {//可持续化线段树
	tot++;
	tree[tot] = tree[now];
	return tot;
}

int build(int now, int l, int r) {
	now = ++tot;
	
	if (l == r) {
		return now;
	}
	
	int mid = (l + r) >> 1;
	tree[now].l = build(tree[now].l, l, mid);
	tree[now].r = build(tree[now].r, mid + 1, r);
	
	return now;
}

int add(int now, int l, int r, int loc, int add_num) {
	now = clone(now);
	
	tree[now].x += add_num;
	
	if (l == r) return now;
	
	int mid = (l + r) >> 1;
	if (loc <= mid) tree[now].l = add(tree[now].l, l, mid, loc, add_num);
		else tree[now].r = add(tree[now].r, mid + 1, r, loc, add_num);
	
	return now;
}

int ask(int now1, int now2, int l, int r, int loc) {
	if (l == r) return l;
	
	int mid = (l + r) >> 1;
	if (loc <= tree[tree[now1].l].x - tree[tree[now2].l].x) return ask(tree[now1].l, tree[now2].l, l, mid, loc);
		else return ask(tree[now1].r, tree[now2].r, mid + 1, r, loc - (tree[tree[now1].l].x - tree[tree[now2].l].x));
}

int main() {
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i].x);
		a[i].num = i;
	}
	sort(a + 1, a + n + 1, cmp);
	
	a[1].xx = ++num;//离散化
	dy[1] = a[1].x;
	for (int i = 2; i <= n; i++)
		if (a[i].x != a[i - 1].x) {
			a[i].xx = ++num;
			dy[num] = a[i].x;
		}
		else a[i].xx = num;
	
	sort(a + 1, a + n + 1, cmp_b);
	
	root[0] = build(0, 1, num);
	
	for (int i = 1; i <= n; i++)
		root[i] = add(root[i - 1], 1, num, a[i].xx, 1);
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &L, &R, &K);
		
		//类似前缀和的思想
		printf("%d\n", dy[ask(root[R], root[L - 1], 1, num, K)]);
	}
	
	return 0;
}