@ConanKID
2021-11-06T04:58:57.000000Z
字数 1661
阅读 131
学习笔记
为什么又要写学习笔记啊
前置知识:权值线段树。
首先利用权值线段树求集合的 Kth 是挺简单的一个事情。相当于一个二分的操作。
现在需要考虑的问题是区间静态 Kth,即给定一个序列 ,多次询问一个区间 中第 小的数。
还是考虑权值线段树上二分。设当前节点为 ,统计 中落在 的左儿子所代表的区间内的数的数量 。若 ,那么证明答案一定在左半区间里,直接向左儿子走。否则令 减去 ,然后向右儿子走。
问题转化为如何快速求出落在一个节点所代表区间内的数的数量。
考虑建出 棵线段树。对于 到 中的每一个 ,都单独建一棵权值线段树,存储把 中的每一个 插入线段树后的结果。同时对于每棵线段树,定义 表示落在节点 代表区间内的数的数量。这样求上面那个东西的时候就只需要把线段树 上的 与线段树 相减即可。
但是仍然有问题:这样做空间会爆炸。
继续分析发现,线段树 与线段树 相比,只多插入了一个数,至多只更改了 个节点( 表示值域)。因此只需要新建 个节点即可。
这里剽一张 OI-Wiki 上的图。
红色表示新建的节点。
这样每次插入操作最多新建 个节点,空间复杂度做到了 。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, len;
int a[maxn], ind[maxn], rt[maxn];
struct PresidentTree {
#define mid (l + r >> 1)
int ls[maxn << 5], rs[maxn << 5], sum[maxn << 5];
int cnt;
int build(int l, int r) {
int k = ++cnt;
if (l == r) return k;
ls[k] = build(l, mid); rs[k] = build(mid + 1, r);
return k;
}
int update(int k, int l, int r, int val) {
int dir = ++cnt; ls[dir] = ls[k]; rs[dir] = rs[k]; sum[dir] = sum[k] + 1;
if (l == r) return dir;
if (val <= mid) ls[dir] = update(ls[k], l, mid, val);
else rs[dir] = update(rs[k], mid + 1, r, val);
return dir;
}
int query(int l, int r, int p, int q, int val) {
if (l == r) return l;
int x = sum[ls[q]] - sum[ls[p]];
if (val <= x) return query(l, mid, ls[p], ls[q], val);
else return query(mid + 1, r, rs[p], rs[q], val - x);
}
} t;
void discrete() {
memcpy(ind, a, sizeof(a));
sort(ind + 1, ind + 1 + n);
len = unique(ind + 1, ind + 1 + n) - ind - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(ind + 1, ind + 1 + len, a[i]) - ind;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
discrete();
t.build(1, len);
for (int i = 1; i <= n; i++)
rt[i] = t.update(rt[i - 1], 1, len, a[i]);
for (int i = 1; i <= m; i++) {
int l, r, k; cin >> l >> r >> k;
cout << ind[t.query(1, len, rt[l - 1], rt[r], k)] << endl;
}
return 0;
}
这玩意儿就是主席树。一个妙妙的数据结构。
几道习题:
没有了。