依旧不给图。 可持久化一般解决的是区间查询类的问题。 可持久化 Trie 基本上都是按着 01 Trie 搞的。 怎么建一棵可持久化 Trie 呢？ 考虑到：如果两个相邻版本的前缀相同的话，我们就从后一个版本当前节点往上一个版本的子节点上连一条边，这样我们就可以保证从每一个根节点出发都可以将所有的版本都过一遍。 先丢个例题：LuoguP4735 经过一番思考，我们令 s[i] 表示序列到 i 的前

前言对拍什么的大家都会，但我今天要来展示一下炒鸡对拍！ 你们普通的对拍无非就是从蓝书上学来的，可是那样的生成数据并不是均匀的！ 举个简单的例子： 你使用 rand 生成了两个集合： $(1，2)$ 和 $(1, 2)$，它们相乘能组成的数只有： $$(1, 2, 4)$$ 也就是说你根本就没找出 3 这个数来！ 如此一来，你生成的数并不均匀，所以这样对拍是可能锅掉的。 那么我们就要使用我们的……

前言本人也没有学多长时间的可持久化数据结构，所以这篇博文多少会有些浅显，还请各位海涵并对学术性错误予以指正。 因为网络的原因我无法把评论区初始化掉，反正我的博客也没人看，而且这里边很多的 Md 和 $\LaTeX$ 都会出现一些奇妙的事情，所以我不会按照之前那种严格的规范来写博文了（避免 $\LaTeX$ 出锅）。 之前出过的锅我就不修了，反正洛谷博客上几乎也有备份，想看可以过去。 Intro”可

前言本篇博文仅仅用来当作个人的学习笔记，创作的标准是让本人自己理解即可，不推荐当作读者的学习资料，如想学习 DAG 上的 Tarjan 算法建议上网搜索详细的资料。 Intro先约定好几个定义哈： 强连通分量（scc）：表示在图上最大的一个子集，满足这个子集中所有点两两间可以相互连通。 流图：在一个 DAG 里，如果存在一个点 $\operatorname{start}$，从这个点出发可以到达所

UPD 2022.7.4：删除了 QQ 表情包（太智障了影响阅读者的心情）。一并删除了一些冗杂的话。 如果你实在是看不懂，那……要不回去复习复习基础的东西？ 如果你没有 DP 基础，建议你去博文里边耐心地翻一翻我之前写过的 DP 入门——《什么是 DP》 无后效性我们在写 DP 的时候，我们只需要记录结果就可以了，而不需要记录决策是什么，这个东西叫做无后效性。 这玩意在设计状态的时候比较重要，不然

之前那个写的太垃圾了……今天我们重写一回。 中考结束之后就可以随心所欲地学 OI 了，先复习一下吧…… 关于把所有人都取关了这件事……我被机惨了，我也懒得再关回来了。（喂我可不想点上百个关注啊！） 这个玩意写的时间比较长，复习一共开始没多久，写的慢一点对我也好……（行，就是我拖更） 行，正题开始。 温馨提示：本片博文含有大量的 $\LaTeX$，我尽量让大家看得舒服点，如果哪里排版炸掉了直接评论区

大坑，填起来比较辛苦，可能慢点。 一直没时间写，估计抽个集训的空就完成了。 比较毒瘤，食用前请确保基础数据结构掌握得差不多了，不然回去学完线性表再来（） 乱入的优先队列一句话优先队列：往一个队列里边扔数，它自动给你排好序等你使用。 来一个十分简（bian）单（tai）的例题： 给定一个正数序列，求第 $k$ 小的子区间和。 $n \le 100000$ 你跟我讲你不知道什么是子区间…… 子区间：

之前那个实在是垃圾到不能再垃圾了……今天必须重写一份。 这个写的会稍微快一点，因为只有一个数据结构，而且也没有大量的 $\LaTeX$，对我也是相当的友好啊。 如有学术问题，请毫不留情地在评论区予以指正。 Definition线段树是一种基于二分思想的二叉树结构，用于在区间上进行信息统计。比起树状数组来用途更加广泛。 实现关于线段树，你需要知道这些常识： 线段树的每个节点都代表一个区间。 线段树

UPD 2022/7/4：删除了一大堆没有意义的内容。 Definition拓扑排序是什么？ 就是在一个 DAG 上边，将所有的点排成一个线性的序列，使得每个点的起点都在终点前边。 那它可以用来干什么呢？ 这可以用来处理一些层次关系，就是如果你想做事件 $A$，必先处理完事件 $B$，类似这样的关系。 实现我们用 BFS 来处理拓扑排序。 我们拿这张图举例： 根据所有的起点都要在终点前边这句话，

Intro树链剖分有什么用呢？目前我唯一已知的用途是支持动态修改树以及求 LCA（常数还小点），还有将你的代码量加上 1 kib。 树链剖分将树分成若干链的形式，这样可以维护路径上的信息。也就是将一个树剖分成一堆序列。树链剖分分为重链剖分，长链剖分，实链剖分（用于 LCT 的剖分）。 大多数情况下，树链剖分一般指重链剖分。 重链剖分将树上任意一条路径划分成不超过 $\log(n)$ 条连续的链，都