线性算法两则
随笔。
- “中位数的中位数”算法求 nth_element
默认元素互异。把所有元素五个一组，每组求出中位数，把所有中位数放到一起求出中位数，让这个中位数在原序列中归位，此后判断
而对于这个中位数，考虑有一半的组中位数小于之。换而言之，至少有
这个代码比较简单，实现了一下。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
pii nth_element(pii* l, pii* p, pii* r) {
constexpr int A = 5, B = 128;
int n = r - l, m = (n - 1) / A + 1;
if (n <= B) return std::nth_element(l, p, r), *p;
pii a[m];
for (pii* i = l; i < r; i += A) {
int m = min<int>(r - i, A);
a[(i - l) / A] = nth_element(i, i + (m >> 1), i + m);
}
pii x = nth_element(a, a + (m >> 1), a + m),
*q = partition(l, r, [&](pii y) { return y < x; });
return p < q ? nth_element(l, p, q) : nth_element(q, p, r);
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, k;
cin >> n >> k;
pii a[n];
for (int i = 0, x; i < n; ++i) cin >> x, a[i] = {x, i};
nth_element(a, a + k, a + n);
return cout << a[k].first << endl, 0;
}- DC3 算法求后缀数组
以前一直觉得很神秘，但学了一下发现实际上是个相当 trivial 的算法。它处理的实际上是对整数序列求后缀数组，要求值域与序列长度同阶。
首先考虑传统算法中一次倍增的基排过程，我们实际上可以把它扩展成这么一个东西：对于每个关键字值域均同阶于序列长度的常数关键字序列，可以在
我们考虑保证序列的最后一个数是序列的唯一最小值；若不满足，在序列末尾加一个再处理就行。考虑将去除第一个元素得到的后缀长度补全至三的倍数，将去除前两个元素得到的后缀长度补全至三的倍数，随后将这两个补全后缀拼起来。将拼起来的后缀三位一考虑采用上面那个基排离散化，然后对这个长度
采用当前位元素为第一关键字，以下一个位置为起始的后缀排名的离散化结果为第二关键字，再跑一遍上面那个基排就能求出每个起始位置为三的倍数的后缀排名离散化后的结果。此后任意两个后缀的排名可比较（同为或同不为三的倍数都能比，一为一不为的话暴力比至多两个字符就能变成同不为），跑个归并就能合并完成。
复杂度
当然一般这个算法的尴尬之处在于线性求出后缀数组之后使用单
以上。