【题目来源】
洛谷：P3834 【模板】可持久化线段树 2 - 洛谷 (luogu.com.cn)
【题目描述】
如题，给定 \(n\) 个整数构成的序列 \(a\)，将对于指定的闭区间 \([l, r]\) 查询其区间内的第 \(k\) 小值。
【输入】
第一行包含两个整数，分别表示序列的长度 \(n\) 和查询的个数 \(m\)。
第二行包含 \(n\) 个整数，第 \(i\) 个整数表示序列的第 \(i\) 个元素 \(a_i\)。
接下来 \(m\) 行每行包含三个整数 $ l, r, k$ , 表示查询区间 \([l, r]\) 内的第 \(k\) 小值。
【输出】
对于每次询问，输出一行一个整数表示答案。
【输入样例】
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
【输出样例】
6405
15770
26287
25957
26287
【算法标签】
《洛谷 P3834 可持久化线段树2》 #线段树# #离散化# #可持久化线段树# #可持久化# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 200005; // 数组大小常量
#define N 200005 // 定义宏，同上面
#define lc(x) tr[x].ch[0] // 左儿子宏定义
#define rc(x) tr[x].ch[1] // 右儿子宏定义int n, m, a[N]; // n: 数组长度，m: 查询次数，a: 原数组
vector<int> v; // 离散化后的有序数组// 主席树节点结构
struct node
{int ch[2]; // 左右儿子编号int s; // 节点值域中有多少个数
}tr[N * 22]; // 每个版本开logN个节点int root[N], idx; // root: 每个前缀的根节点，idx: 节点计数器// 构建初始空树（实际上可以不用，但这里保留了）
void build(int &x, int l, int r)
{x = ++idx;if (l == r) return;int m = l + r >> 1;build(lc(x), l, m);build(rc(x), m + 1, r);
}// 插入操作，建立新版本
void insert(int x, int &y, int l, int r, int v)
{y = ++idx; // 创建新节点tr[y] = tr[x]; // 复制旧节点信息tr[y].s++; // 节点计数加1if (l == r) return; // 叶子节点int m = l + r >> 1; // 双指针同步搜索if (v <= m) // 值在左子树{insert(lc(x), lc(y), l, m, v);}else // 值在右子树{insert(rc(x), rc(y), m + 1, r, v);}
}// 查询区间第k小
int query(int x, int y, int l, int r, int k)
{if (l == r) return l; // 找到第k小的数int m = l + r >> 1; // 双指针同步搜索int s = tr[lc(y)].s - tr[lc(x)].s; // 左子树的数字个数if (k <= s) // 第k小的数在左子树{return query(lc(x), lc(y), l, m, k);}else // 第k小的数在右子树{return query(rc(x), rc(y), m + 1, r, k - s);}
}// 获取值x在离散化数组中的位置（从1开始）
int getid(int x)
{return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}int main()
{cin >> n >> m; // 读入数组长度和查询次数for (int i = 1; i <= n; i++){cin >> a[i];v.push_back(a[i]); // 保存原始值用于离散化}// 离散化处理sort(v.begin(), v.end()); // 排序v.erase(unique(v.begin(), v.end()), v.end()); // 去重int vn = v.size(); // 离散化后的数值范围大小// 构建主席树for (int i = 1; i <= n; i++){insert(root[i - 1], root[i], 1, vn, getid(a[i]));}// 处理查询while (m--){int l, r, k;cin >> l >> r >> k;int id = query(root[l - 1], root[r], 1, vn, k) - 1; // 查询第k小cout << v[id] << endl; // 输出离散化前的原始值}return 0;
}
【运行结果】
5 5
25957 6405 15770 26287 26465
2 2 1
6405
3 4 1
15770
4 5 1
26287
1 2 2
25957
4 4 1
26287