中国剩余定理是用来合并同余方程组的算法，当满足模数两两互质时有一种巧妙的构造解的方法，当不满足模数互质时同样可以通过两两合并的方式得到最终解。

莫队算法是利用平衡复杂度的思想来优化暴力算法，通常是通过均值不等式求出一个最优复杂度。

简介 LCT 利用 Splay 对树进行虚实链剖分，同一实链上的结点处在同一个 Splay 中，排序的关键字是深度。因此 Splay 的中序遍历就是树的从上到下的有序的树链。虚边是只记录父结点，父结点不记录子结点。介绍一下几个重要函数。 isroot(x) 判断 xxx 是否为根，只需要判断 fa(x)fa(x)fa(x) 是否含有 xxx 的指针即可。 123bool isroot(int x) ...

简介 当涉及区间之间的连边操作时，可以考虑使用线段树优化建图，首先建立线段树，让父结点指向子结点或相反，边权为零，然后就会发现无论是最短路还是连通性，都与原图无区别。 [CF786B] Legacy 在宇宙中一共有 nnn 个星球标号为 1∼n1 \sim n1∼n。Rick 现在身处于标号为 sss 的星球(地球)但是他不知道 Morty 在哪里。 众所周知，Rick 有一个传送枪，他用这把枪 ...

一句话说明，在 Kruskal 算法中的并查集合并两点所在连通块这一步，新建一个虚点并将左右连通块代表点经过虚点连接起来，用二叉树的结构记录并查集的合并顺序即加边顺序。

通过分治算法，将多项式在 O(nlog(n)) 的复杂度内进行变换，然后 O(n) 计算，最后进行一次 O(nlog(n)) 的逆变换进行求出位运算卷积。

简介 IO 优化通常对于程序的常数提升并不是很大，但是在数据量比较大，大概 10610^6106 级别的时候就要考虑加上 IO 优化了，如果数据量不大反而可能导致负优化。 基本原理是 C++ 标准库对于格式处理的比较多，而我们想要的一般来说只是输入和输出整数，所以自己实现起来常数会略有提升。 READ / WRITE 输入的原理是从输入流中读取字符，过滤出非整数字符并记录是否含有负号，然后处理一段 ...

动态 DP 是一种带修求 DP 值的技术，通过广义矩阵乘法维护各 DP 值之间的关系，然后修改的时候修改转移矩阵即可达到带修求 DP 值的目的，可以结合树剖将树上的某些 DP 转化成重儿子和轻儿子之间的转化，然后用树剖线段树维护广义矩阵之积。

线段树合并指建立一棵新的线段树，每个节点都是原来两棵树对应结点的合并后的结果，常与树上差分或者树形 DP 一起使用，用于维护每个点有多个信息，并且需要合并之后求最大值或者某些线段树支持的操作。

可持久化数据结构包括可持久化数组，可持久化并查集，可持久化线段树，都是以复用现有结点的思想记录各个历史版本，从而做到在较低的空间复杂度储存每一次修改后数据结构中的数据。