A. Accelerator 题意 给定 $n$ 个正整数 $a_1,a_2,…,a_n$，它们总共有 $n!$ 种 permutation。 对于每一种 permutation $a_{k_1},a_

介绍 一维差分可以用于解决以下问题： 给定一系列的区间加/减操作，最后询问整个数组的元素。 那么二维差分就可以解决： 给定一系列的矩阵加/减操作，最

介绍 树套树常常用于解决一些二维数点问题。 经典的问题如：矩阵内查询和/最大值，更新矩阵内一个点的值等等。 在介绍树套树之前，先简单讲一下树状数组

本文主要记录一些组合数学的常用模型。 组合数 $C(n,m)$ $C_n^0 = C_n^n = 1$ $C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$ $C_n^k = \frac{n!}{k!(n-k)!}$ $\sum\limits_{i=l}^r C_i^m = C_{r+1}^{m+1}-C_{l}^{m+1}$ • 注：$0! = 1, (0!)^{-1} = 1$ 证明公式2 $n$ 个中选 $k$ 个， 考虑 $n$ 个元素中的

拉格朗日插值 给定 $n$ 个点，我们可以确定唯一的最高 degree 为 $(n-1)$ 的多项式。 设多项式为 $f(x)$，第 $i$ 个点的坐标为 $(x_i,y_i)$，那么这个多项式

定义 闭合子图 对于一个 有向图 $G=(V,E)$，它的一个闭合子图 $G'=(V’,E’)$ 满足： $\forall u \in V'$，如果 $(u,v) \in E$，则 $v \in V’, (u,v) \in E'$ 简单来说，就是对于子图中的每

曼哈顿距离 定义两个点 $A(x_1,y_1), B(x_2,y_2)$，则 $A,B$ 之间的曼哈顿距离为： $$d(A,B) = |x_1 - x_2| + |y_1 - y_2|$$ 曼哈顿距离的性质： 对称性：$d(A,B) = d(B,A)$ 三角形不

介绍 这篇博客主要介绍一些并查集的高级应用。 目前我所知的并查集应用有： 权值并查集 可撤销并查集 可持久化并查集（还没学） 权值并查集 略，目前我所知的

介绍 最短路径树是指一个图，在以 某个点 为根，跑出来单源最短路以后，形成的树结构。 具体建树方法就是：在跑单源最短路的时候，用一个 pre[] 数组记录一下每

介绍 最小生成树就是给定一张边有权值的图，求一个生成树使得边权和最小。 最小生成树有着以下几个性质： 最小生成树不唯一，次小生成树可以通过枚举非树