注意事项 Set中的Comparator定义 在定义Set的Comparator时，一定要小心保证元素不会因为定义被判定为重复，例如： int cnt[maxn]; struct Cmp {

模版 代码 struct SA { int n, sa[maxn], rk[maxn<<1], oldrk[maxn<<1], cnt[maxn], id[maxn], key1[maxn], height[maxn]; // 注意 rk[maxn<<1] oldrk[maxn<<1] char s[maxn]; int m = 127; bool cmp(int i, int j, int w) { return oldrk[i] == oldrk[j] && oldrk[i+w] == oldrk[j+w]; } void init(string& ss) { n = ss.size(); // LOG(n); for (int i = 1; i <= n; i++) s[i] = ss[i-1]; for (int i = 1;

介绍 二维ST表就是在一维的ST表上加一个维度，这样可以 $O(nm\log n \log m)$ 内预处理以后，$O(1)$ 询问一个矩阵的最大/最小值。 例题 例1 洛谷P2216[

C. Constellations 题意 二维平面中有 $n$ 个点，一开始每个点都属于自己的一组。 有 $n-1$ 轮合并过程，每次合并选择距离最近的两组点进行合并，两组点 $A,B$ 之间的距离定义为： $$d(A,B)

介绍 二项式反演是一种特殊的容斥，用来解决 “恰好选 $k$ 个的方案有多少种” 的问题。 一般，我们可以求出 “至多/至

G. Rafting Trip 题意 给定一个 $n \times m$ 的网格，每个网格要么是河流，要么是陆地。 如果是河流，那么它一定是上下左右四个方向之一，代表走到这个位置，下一个位置就

介绍 吉司机线段树可以做到： 区间最大/最小操作（对一个区间内的所有数取 max 或者 min） 维护区间历史最值 我们直接看一道例题： 题意 给定一个数组 $a_1, a_2, …

老是忘，简单记录一下吧。 介绍 一个边权仅为 $0,1$ 的图中跑最短路可以直接用 bfs。 维护一个 deque，每次更新 dis[v] 时就将 v push进去，如果 w(u,v) == 0 就p

介绍 给定一个无向图，找出图中所有的三元环，每个环只能被计一次。(比如 $a,b,c$ 和 $b,a,c$ 都是同一个环)。 我们先处理出每个点的 degree，然后建一个新的图

公平组合游戏 公平组合游戏 Impartial Combinatorial Game (ICG) 满足以下性质： 有 $2$ 名玩家。 $2$ 名玩家轮流操作，在一个游戏集合中选其中一个进行操作。 对于任意一个合法的局面，当前