POJ 2104 第K小数(不带修主席树模板)

不带修主席树模板

这篇博客代码挺好的 https://blog.csdn.net/creatorx/article/details/75446472

这篇博客图好评 https://blog.csdn.net/qq_39809664/article/details/79934516

#include <iostream>
#include <algorithm>
#define ll long long
#define imid int mid=(left+right)/2;
using namespace std;
int n, m, cnt, a[100005], t[100005], root[100005];
struct node
{
	int l;
	int r;
	int sum;
	node() { sum = 0; }
}tree[100005 * 20];
void init()
{
	root[0] = 0;
	tree[0].l = tree[0].r = tree[0].sum = 0;
	cnt = 1;
}
void build(int num, int&rot, int left, int right)
{
	tree[cnt] = tree[rot];
	rot = cnt;
	cnt++;
	tree[rot].sum++;
	if (left == right)
		return;
	imid;
	if (num <= mid)
		build(num, tree[rot].l, left, mid);
	else
		build(num, tree[rot].r, mid + 1, right);
}
int query(int pre, int nex, int num, int left, int right)
{
	int s = tree[tree[nex].l].sum - tree[tree[pre].l].sum;
	if (left == right)
		return left;
	imid;
	if (num <= s)
		return query(tree[pre].l, tree[nex].l, num, left, mid);
	else
		return query(tree[pre].r, tree[nex].r, num - s, mid + 1, right);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		t[i] = a[i];
	}
	sort(t + 1, t + 1 + n);
	cnt = unique(t + 1, t + 1 + n) - t - 1;
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(t + 1, t + 1 + n, a[i]) - t;
	init();
	for (int i = 1; i <= n; i++)
	{
		root[i] = root[i - 1];
		build(a[i], root[i], 1, n);
	}
	int ql, qr, k;
	while (m--)
	{
		scanf("%d%d%d", &ql, &qr, &k);
		int ans = query(root[ql - 1], root[qr], k, 1, n);
		printf("%d\n", t[ans]);
	}
}