Lyndon 分解学习笔记
定义 一个字符串 s 是 Lyndon Word,当且仅当 s 是其所有后缀中字典序最小的; 将字符串 s 分为若干部分 s_1s_2\cdots s_m,使得每个 s_i 都是 Lyndon 串,且 \foral...
定义 一个字符串 s 是 Lyndon Word,当且仅当 s 是其所有后缀中字典序最小的; 将字符串 s 分为若干部分 s_1s_2\cdots s_m,使得每个 s_i 都是 Lyndon 串,且 \foral...
区间最值操作 & 区间历史最值 本文讲解了吉老师在 2016 年集训队论文(见参考资料)中提到的使用线段树维护区间最值操作和区间历史最值的方法。 前置知识:懒标记线段树。 区间最值操作 首先假设我们有一个序列...
高维前缀和 一维前缀和是形如这样的递推式: s_i=s_{i-1}+a_i 它也可以扩展到二维: s_{i,j}=s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}+a_{i,j} 比较容易发现它是个...
有时候用哈希总会感觉心里不稳,怕脸黑撞生日悖论 FST 或者被别人 Hack 之类的,而多模哈希有太慢。今天逛 CF 评论区 看见了一种比较优秀的做法,再此 mark 一下。 ull mix(ull o) { ...
参考自 OI Wiki - 回文树 回文树 简介 回文树也叫回文自动机(PAM),每个状态表示一个本质不同的回文子串。 与后缀自动机相似,回文树由状态节点,转移边,fail 链和长度 len 四部分组成。一个节点的转...