冷滟泽的个人博客冷滟泽的个人博客

学习笔记

OI,学习笔记

Lyndon 分解学习笔记

lengyanze 阅读(80) 评论(0)

定义 一个字符串 s 是 Lyndon Word,当且仅当 s 是其所有后缀中字典序最小的; 将字符串 s 分为若干部分 s_1s_2\cdots s_m,使得每个 s_i 都是 Lyndon 串,且 \foral...

OI,学习笔记

区间最值操作 & 区间历史最值学习笔记

lengyanze 阅读(48) 评论(0)

区间最值操作 & 区间历史最值 本文讲解了吉老师在 2016 年集训队论文(见参考资料)中提到的使用线段树维护区间最值操作和区间历史最值的方法。 前置知识:懒标记线段树。 区间最值操作 首先假设我们有一个序列...

OI,学习笔记

Hash 的一种优秀方法

lengyanze 阅读(90) 评论(0)

有时候用哈希总会感觉心里不稳,怕脸黑撞生日悖论 FST 或者被别人 Hack 之类的,而多模哈希有太慢。今天逛 CF 评论区 看见了一种比较优秀的做法,再此 mark 一下。 ull mix(ull o) { ...

OI,学习笔记

回文树/最小回文划分学习笔记

lengyanze 阅读(54) 评论(0)

参考自 OI Wiki - 回文树 回文树 简介 回文树也叫回文自动机(PAM),每个状态表示一个本质不同的回文子串。 与后缀自动机相似,回文树由状态节点,转移边,fail 链和长度 len 四部分组成。一个节点的转...