Shirakami Lynrics

一些OI模板总结。

一些OI经典题目。

一些OI经典题目。

关于一种非旋随机化平衡树——FHQ-Treap。

简介对于个长度为 $n$ 的字符串 $s$。定义函数 $z[i]$ 表示 $s$ 和 $s[i,n-1]$（即以 $s[i]$ 开头的后缀）的最长公共前缀（LCP）的长度。$z$ 被称为 $s$ 的 Z 函数。特别地，$z[0] = 0$。 国外一般将计算该数组的算法称为 Z Algorithm，而国内则称其为 扩展 KMP。 示例下面若干样例展示了对于不同字符串的 Z 函数： $z(\mathtt{aaaaa}) = [0, 4, 3, 2, 1]$ $z(\mathtt{aaabaab}) = [0, 2, 1, 0, 2, 1, 0]$ $z(\mathtt{abacaba}) = [0, 0, 1, 0, 3, 0, 1]$ 朴素算法Z 函数的朴素算法复杂度为 $O(n^2)$： 1234567vector<int> z_function_trivial(string s) { int n = (int)s.length(); vector<int> z(n); for (int i = 1; i < n; ++i) wh ...

关于一种简单的数据结构——树状数组。

关于一种简单的基础字符串匹配算法——KMP算法。

关于一种暴力数据结构——珂朵莉树！

关于筛法及其优化。

关于四边形不等式。