255. 第K小数 - AcWing题库 给定长度为 的整数序列 ，下标为 。
现在要执行 次操作，其中第 次操作为给出三个整数 ，求 (即 的下标区间 )中第 小的数是多少。
输入格式
第一行包含两个整数 和 。
第二行包含 个整数，表示整数序列 。
接下来 行，每行包含三个整数 ，用以描述第 次操作。
输出格式
对于每次操作输出一个结果，表示在该次操作中，第 小的数的数值。
每个结果占一行。
数据范围
输入样例：
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3输出样例：
5
6
3思路
区间第K小数是一个静态问题, 查询不会修改原本的内容, 有很多种解法：
- 归并树, 时间, 不支持修改, 且实现很麻烦
- 划分树, 时间, 空间 , 不支持修改
- 线段树套平衡树, 时间 , 空间 , 支持修改
- 可持久化线段树, 时间, 空间, 不支持修改
可持久化线段树—主席树也可以套平衡树。
该题建立线段树时需要根据数值建立, 即 代表 的个数。再看数据范围, 每个数值的范围很大, 但总个数只有1e5个, 可以进行离散化处理。
先不考虑区间, 怎么求整体的第k小数？可以通过二分优化方法查找：
若 中点数量 , 那么第K小数一定不在 中, 直接搜左边区间。
同理, 若 , 则答案一定在右区间。
接着再考虑 的情况, 跟 Tire 树 可持久化 类似, 从第一个数加到第R个数时, 查询当前的版本 就能得到 的第K小数。
至于 区间, 可以找出 的个数 , 跟 的个数 , 根据个数的性质, 让 就是区间 的个数。因此在二分时搜索一个满足条件 的最小的 即可。
线段树节点开的个数就是 加上因为修改新加的节点数 。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e5 + 10, M = 1e4 + 10;
int a[N];
struct Node {
int l, r;
int cnt;
}tr[N * 4 + N * 17];
int root[N], idx;
vector<int> nums;
int n,m;
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.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 q, int p, int l, int r, int k)
{
if(l == r) return r;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if(k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n;i ++)
{
cin >> a[i];
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(),nums.end()), nums.end());
root[0] = build(0, nums.size() - 1);
for(int i = 1; i <= n; i++)
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
while(m--)
{
int l, r, k;
cin >> l >> r >> k;
cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << endl;
}
return 0;
}