【模板】可持久化线段树 2
进算竞小群加我
这是个非常经典的可持久化权值线段树入门题——静态区间第 $k$ 小。
如题,给定 $n$ 个整数构成的序列 $a$,将对于指定的闭区间 $[l, r]$ 查询其区间内的第 $k$ 小值。
第一行包含两个整数,分别表示序列的长度 $n$ 和查询的个数 $m$。
第二行包含 $n$ 个整数,第 $i$ 个整数表示序列的第 $i$ 个元素 $a_i$。
接下来 $m$ 行每行包含三个整数 $ l, r, k$ , 表示查询区间 $[l, r]$ 内的第 $k$ 小值。
对于每次询问,输出一行一个整数表示答案。
- 对于 $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$。
分析
前置知识:权值线段树求全局第$k$小
我们知道全局第$k$小是在权值线段树上二分
找到前缀数量为大于等于$k$的第一个位置
拓展:求静态区间第$k$小
对于要求的每一个区间我们可以将其转化成全局求第$k$小
但是所有区间是$n^2$的复杂度
我们不可能对所有的区间建一颗权值线段树
但是我们可以对前缀建权值线段树
这样只用建$n$棵权值线段树
但是每一棵线段树的空间复杂度是$O(n)$的 (如果$|a_i|>n$ 就可以进行离散化,将值域映射到$[1,n]$)
如果全建出来必定会$MLE$
但是我们发现如果进行单点修改,那么会修改$\lceil log_2n \rceil+1$ 个节点,剩下的节点都是公用的
所以如果我们每次操作只建需要进行修改的节点,那么最多只会有$n\lceil log_2n \rceil+n$ 个节点会修改
加上一开始建树的节点$2n-1$ 一共有$n\lceil log_2n \rceil+3n-1$ 个节点
很好的避免了$MLE$ , 一般的$n\le 2*10^5$ 也就是$log_2n<18$
$n\lceil log_2n \rceil+3n-1\le18n+3n-1$
$n\lceil log_2n \rceil+3n-1\le21n-1$
所以开$21n$个节点就够了,当然也可以稍微开的多一点
code
// Luogu P3834 【模板】可持久化线段树 2
// https://www.luogu.com.cn/problem/P3834 2024-02-27 20:26:19
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
constexpr int N = 2E5 + 10LL;
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
int n, q, a[N];
vector<int> v;
struct node {
int ch[2];
int s;
} tr[N * 22];
int root[N], idx;
void build(int &x, int l, int r) {
x = ++idx;
if (l == r) return;
int mid = l + r >> 1;
build(lc(x), l, mid), build(rc(x), mid + 1, r);
}
void insert(int x, int &y, int l, int r, int v) {
y = ++idx, tr[y] = tr[x], tr[y].s++;
if (l == r) return;
int mid = l + r >> 1;
if (v <= mid)
insert(lc(x), lc(y), l, mid, v);
else
insert(rc(x), rc(y), mid + 1, r, v);
}
int query(int x, int y, int l, int r, int k) {
if (l == r) return l;
int mid = l + r >> 1;
int s = tr[lc(x)].s - tr[lc(y)].s;
if (k <= s)
return query(lc(x), lc(y), l, mid, k);
else
return query(rc(x), rc(y), mid + 1, r, k - s);
}
int get_id(int x) { return lower_bound(all(v), x) - begin(v) + 1; }
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i], v.emplace_back(a[i]);
sort(all(v));
v.erase(unique(all(v)), end(v));
int vn = v.size();
build(root[0], 1, vn);
for (int i = 1; i <= n; i++)
insert(root[i - 1], root[i], 1, vn, get_id(a[i]));
while (q--) {
int l, r, k;
cin >> l >> r >> k;
auto it = query(root[r], root[l - 1], 1, vn, k);
cout << v[--it] << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}