255. 第K小数 - AcWing题库

给定长度为 N 的整数序列 A，下标为 1∼N。

现在要执行 M 次操作，其中第 i 次操作为给出三个整数 li,ri,ki，求 A[li],A[li+1],…,A[ri] (即 A 的下标区间 [li,ri])中第 ki 小的数是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示整数序列 A。

接下来 M 行，每行包含三个整数 li,ri,ki，用以描述第 i 次操作。

输出格式

对于每次操作输出一个结果，表示在该次操作中，第 k 小的数的数值。

每个结果占一行。

数据范围

N≤105,M≤104,|A[i]|≤109

输入样例：

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

输出样例：

5
6
3

解析： 

本题离散化后，线段树的节点保存的是某个值域区间和区间内的数的个数，思路参考D 无限的韵律源点 (STL_set +对顶堆 , 线段树+离散化 , * * * * *)-CSDN博客的线段树做法

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int INF = 0x3f3f3f3f;
const LL Mod = 2147483648;
const int N = 1e5 + 10, M = N * 25;
int n, m;
int a[N];
vector<int>num;
struct Node {
	int l, r;
	int cnt;
}tr[N*4+N*17];
int root[N],idx;

int find(int x) {
	return lower_bound(num.begin(), num.end(), x) - num.begin();
}

int build(int l, int r) {
	int p = ++idx;
	if (l == r)return p;
	int mid = l + r >> 1;
	tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
	return p;
}

int insert(int p, int l, int r, int x) {
	int q = ++idx;
	tr[q] = tr[p];
	if (l == r) {
		tr[q].cnt++;
		return q;
	}
	int mid = l + r >> 1;
	if (x <= mid)tr[q].l = insert(tr[p].l, l, mid, x);
	else tr[q].r = insert(tr[p].r, mid + 1, r, x);
	tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
	return q;
}

int query(int p, int q, int l, int r, int k) {
	if (l == r) {
		return l;
	}
	int mid = l + r >> 1;
	int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
	if (k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);
	else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		num.push_back(a[i]);
	}
	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()), num.end());

	//cout << "__________++++++++++++++++++++++" << endl;

	root[0] = build(0, num.size() - 1);
	//cout << "____________________________" << endl;
	for (int i = 1; i <= n; i++) {
		root[i] = insert(root[i - 1], 0, num.size() - 1, find(a[i]));
	}

	//cout << "_____________________________" << endl;

	int l, r, x;
	while (m--) {
		scanf("%d%d%d", &l, &r, &x);
		printf("%d\n", num[query(root[l - 1], root[r], 0, num.size() - 1, x)]);
	}
	return 0;
}