【模板】可持久化线段树 2
题目背景
这是个非常经典的可持久化权值线段树入门题——静态区间第 \(k\) 小。
数据已经过加强，请使用可持久化权值线段树。同时请注意常数优化。
题目描述
如题，给定 \(n\) 个整数构成的序列 \(a\)，将对于指定的闭区间 \([l, r]\) 查询其区间内的第 \(k\) 小值。
输入格式
第一行包含两个整数，分别表示序列的长度 \(n\) 和查询的个数 \(m\)。
第二行包含 \(n\) 个整数，第 \(i\) 个整数表示序列的第 \(i\) 个元素 \(a_i\)。
接下来 \(m\) 行每行包含三个整数 $ l, r, k$ , 表示查询区间 \([l, r]\) 内的第 \(k\) 小值。
输出格式
对于每次询问，输出一行一个整数表示答案。
样例 #1
样例输入 #1
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1
样例输出 #1
6405
15770
26287
25957
26287
提示
样例 1 解释
\(n=5\)，数列长度为 \(5\)，数列从第一项开始依次为\(\{25957, 6405, 15770, 26287, 26465\}\)。
- 第一次查询为 \([2, 2]\) 区间内的第一小值，即为 \(6405\)。
- 第二次查询为 \([3, 4]\) 区间内的第一小值，即为 \(15770\)。
- 第三次查询为 \([4, 5]\) 区间内的第一小值，即为 \(26287\)。
- 第四次查询为 \([1, 2]\) 区间内的第二小值，即为 \(25957\)。
- 第五次查询为 \([4, 4]\) 区间内的第一小值，即为 \(26287\)。
数据规模与约定
- 对于 \(20\%\) 的数据，满足 \(1 \leq n,m \leq 10\)。
- 对于 \(50\%\) 的数据，满足 \(1 \leq n,m \leq 10^3\)。
- 对于 \(80\%\) 的数据，满足 \(1 \leq n,m \leq 10^5\)。
- 对于 \(100\%\) 的数据，满足 \(1 \leq n,m \leq 2\times 10^5\)，\(|a_i| \leq 10^9\)，\(1 \leq l \leq r \leq n\)，\(1 \leq k \leq r - l + 1\)。
先看这篇博客
P3919 【模板】可持久化线段树 1（可持久化数组） - 沙野博士 - 博客园 (cnblogs.com)
本题要求查询区间第k小，也就是对于给定区间[l,r] ,将其中的数按从小到大排序，找到其中第k个元素。
由持久化线段树1可知，我们可以用线段树维护一个可持久化数组，这道题要维护的数组就是这些元素的桶这个数组。按位置每一个位置就是一个历史版本。
实现过程中，最好先建一个完整的空的线段树，省去判断指针是否为空的麻烦。
/*
P3834 【模板】可持久化线段树 2
*/
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 2e5+10;
inline int read()
{
register char c = getchar(); register int x = 0 , f = 0;
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n;
int A[N] , B[N];
struct node{
node *ls , *rs;
int size;
node(int size = 0) : ls(NULL) , rs(NULL) , size(size){}
}*rot[N];
void Init()
{
//int *B = new int [n + 1];
for(int i = 1 ; i <= n ; ++i) B[i] = A[i];
sort(B + 1 , B + 1 + n);
for(int i = 1 ; i <= n ; ++i) A[i] = lower_bound(B + 1 , B + 1 + n , A[i]) - B;
}
void build(node *&rt , int l , int r)
{
rt = new node;
if(l == r) return ;
int mid = (l + r) >> 1;
build(rt->ls , l , mid);
build(rt->rs , mid+1 , r);
}
void modify(node *&rt , node *lst , int l , int r , int pos)
{
rt = new node; rt->size = lst->size + 1;
if(l == r) return ;
int mid = (l + r) >> 1;
if(pos <= mid)
rt->rs = lst->rs , modify(rt->ls , lst->ls , l , mid , pos);
else
rt->ls = lst->ls , modify(rt->rs , lst->rs , mid+1 , r , pos);
}
int query(node *L , node *R , int l , int r , int k)
{
if(l == r) return l;
int num = (R->ls ? R->ls->size : 0) - (L->ls ? L->ls->size : 0);
int mid = (l + r) >> 1;
if(k <= num)
return query(L->ls , R->ls , l , mid , k);
else
return query(L->rs , R->rs , mid+1 , r , k - num);
}
int main()
{
int m , l , r , k;
n = read(); m = read();
for(int i = 1 ; i <= n ; ++i)
A[i] = read();
Init();
// cout << "YES" << '\n';
build(rot[0] , 1 , n);
// cout << "YES" << '\n';
for(int i = 1 ; i <= n ; ++i)
modify(rot[i] , rot[i-1] , 1 , n , A[i]);
// cout << "YES" << '\n';
while(m--)
{
l = read(); r = read(); k = read();
printf("%d\n" , B[query(rot[l-1] , rot[r] , 1 , n , k)]);
}
return 0;
}