Blog of RuSun

可持久化线段树模板

发表于 2021-12-19 分类于 OI
本文字数： 1.6k 阅读时长 ≈ 1 分钟

标签：模板可持久化线段树

用于维护历史多版本的线段树。

阅读全文 »

后缀数组(SA)模板

发表于 2021-12-20 分类于 OI
本文字数： 1.2k 阅读时长 ≈ 1 分钟

标签：模板 SA

用于快速求后缀串的排名。

阅读全文 »

后缀自动机（SAM）模板

发表于 2021-12-23 分类于 OI
本文字数： 1.4k 阅读时长 ≈ 1 分钟

标签：模板 SAM

用于快速求解字符串子串问题。

阅读全文 »

多项式全家桶

发表于 2022-02-22 分类于 OI
本文字数： 9.9k 阅读时长 ≈ 9 分钟

标签：模板多项式 CRT

NTT，求逆，积分微分，对数指数，快速幂，除法。

阅读全文 »

子集卷积模板

发表于 2022-03-24 分类于 OI
本文字数： 2k 阅读时长 ≈ 2 分钟

标签：模板 FWT/FMT

快速子集卷积。

阅读全文 »

左偏树模板

发表于 2021-11-22 分类于 OI
本文字数： 1.9k 阅读时长 ≈ 2 分钟

标签：模板左偏树

用于可并堆。

阅读全文 »

带修莫队模板

发表于 2022-01-25 分类于 OI
本文字数： 2.6k 阅读时长 ≈ 2 分钟

标签：模板带修莫队

用于带修改的莫队问题。

阅读全文 »

广义SAM模板

发表于 2022-06-19 分类于 OI
本文字数： 2.4k 阅读时长 ≈ 2 分钟

标签：模板广义SAM

多串问题。

阅读全文 »

扩展 BSGS 模板

发表于 2022-01-21 分类于 OI
本文字数： 1.7k 阅读时长 ≈ 2 分钟

标签：模板 BSGS

用于快速求方程 $a ^ x = b$ 的最小非负整数解。

阅读全文 »

扫描线模板

发表于 2022-01-22 分类于 OI
本文字数： 2.2k 阅读时长 ≈ 2 分钟

标签：模板扫描线

用于快速求矩形面积并。

阅读全文 »

拉格朗日插值模板

发表于 2022-01-09 分类于 OI
本文字数： 1.1k 阅读时长 ≈ 1 分钟

标签：模板拉格朗日插值

已知 $n$ 个点，快速确定一个 $n - 1$ 次多项式。

阅读全文 »

整体二分模板

发表于 2022-03-03 分类于 OI
本文字数： 3.3k 阅读时长 ≈ 3 分钟

标签：整体二分

区间、值域问题的强大算法。

阅读全文 »

斯坦纳树模板

发表于 2022-08-30 分类于 OI
本文字数： 2.8k 阅读时长 ≈ 3 分钟

标签：模板斯坦纳树

求最小斯坦纳树。

阅读全文 »

斯特林数

发表于 2022-07-01 分类于 OI
本文字数： 2.3k 阅读时长 ≈ 2 分钟

标签：组合数学斯特林数斯特林反演

斯特林数相关。

阅读全文 »

最大流模板

发表于 2021-11-15 分类于 OI
本文字数： 1.6k 阅读时长 ≈ 1 分钟

标签：模板最大流最小割

dinic

阅读全文 »

最小割树模板

发表于 2022-03-14 分类于 OI
本文字数： 5.6k 阅读时长 ≈ 5 分钟

标签：模板树上倍增最小割树

做 $n$ 次最小割，$\log n$ 回答任意两点最小割。

阅读全文 »

最小直径生成树模板

发表于 2022-08-07 分类于 OI
本文字数： 3.1k 阅读时长 ≈ 3 分钟

标签：模板 MDST

求最小直径生成树。

阅读全文 »

最小表示法模板

发表于 2021-12-06 分类于 OI
本文字数： 811 阅读时长 ≈ 1 分钟

标签：模板最小表示法

我们定义循环是指不断将第一个字符放到最后。

显然，经过循环之后，一共会产生 $n$ 个字符串（ $n$ 为字符串长度）。

其中最小的就是最小表示法。

阅读全文 »

最短路模板

发表于 2021-11-15 分类于 OI
本文字数： 9.4k 阅读时长 ≈ 9 分钟

标签：模板最短路

用于求解图的最短路问题。

阅读全文 »

李超线段树模板

发表于 2022-01-25 分类于 OI
本文字数： 2.9k 阅读时长 ≈ 3 分钟

标签：模板李超线段树

快速求某个点在若干函数的最值，支持添加函数的操作。

阅读全文 »