本文主要是介绍255. 第K小数 (可持久化线段树，模板题，离散化，* * )，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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;
}这篇关于255. 第K小数 (可持久化线段树，模板题，离散化，* * )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
