分类: 笔记 - Acoipp 的个人博客

七月 14, 2024

Link-Cut Tree（动态树）本文章中的部分代码和思路来自于 Link Cut Tree - OI Wiki。定义LCT 用来解决动态树的问题，即...

七月 03, 2024

平衡树本文章中的部分代码和思路来自于 Treap - OI Wiki 和 Splay 树 - OI Wiki。平衡树是二叉查找树的一种，二叉查找树有一个...

六月 30, 2024

引入我们都知道，树链剖分的时间复杂度如下表：链修改链查询子树修改子树查询时间复杂度 $O(\log^2 n)$ $O(\log^2...

五月 23, 2024

THUSC 2024 简要题解T1 弃光魔使的能量塔题意题目大意，给定 $T,d$，$T$ 组数据，每组数据给出 $n_1,n_2,\dots,n_d,p...

四月 23, 2024

后缀数组（SA）定义给定一个字符串 $S{1 \dots n}$，你需要对这个字符串的 $n$ 个后缀按照字典序排序，排序后的下标数组就是 $sa_i$，...

四月 22, 2024

斯特林数快速计算第二类斯特林数设 $\begin{Bmatrix} n \\ m\end{Bmatrix}$ 表示 $n$ 个数划分成 $m$ 个集合的方...

四月 22, 2024

回文自动机（PAM）回文自动机是一种高效处理回文串相关操作的数据结构，这一节我们专门描述回文自动机以及其扩展应用。定理：一个字符串中的本质不同回文子串...

四月 03, 2024

拉格朗日插值动态拉格朗日插值插值公式（$n$ 个点 $x_i,y_i$ 确定一个 $n-1$ 次多项式，求出点 $x$ 处的取值）： $$f(x) &#x...

四月 03, 2024

快速沃尔什变换 FWT给定两个数组 $A,B$，求出 $A,B$ 经过下列变换之后得到的 $C$ 数组，快速计算。 $$C_i = \sum_{...