【笔记/模板】最小生成树
www.luogu.com.cn
概念/定义
一个连通图的生成树是一个极小的连通子图，它包含图中全部的 nnn 个顶点，但只有构成一棵树的 n−1n-1n−1 条边。而最小生成树就是一个带权图的生成树，并且使得原图中边的权值最小的生成树 ，所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。
思路（Kruskal适用于稀疏图，Prim适用于稠密图）
Kruskal 算法
整体思路：
Kruskal 是一种使用贪心 + 排序+并查集的最小生成树算法，通过每两个点之间的最小距离累加并且将两个点合并，最终生成一种生成树的算法。
时间复杂度：
O(mlogm)O(m \log m)O(mlogm)（其中 mmm 点表示边数）。
代码实现：
1234567891011struct Edge{ int u, v, w; // 存下入边，出边，权值 bool operator < (const Edge &rhs) const // 重载运算符，将权值为第一关键词非降序排序 { if (w != rhs.w) return ...
【模板】线段树
模板#111
www.luogu.com.cn
代码
init
123456789#define lc u << 1#define rc u << 1 | 1int a[N]; // 初始数组struct Tree{ int l, r, sum; // 分别表示左儿子，右儿子的节点以及该节点的区间和 int add; // 懒惰标记} tr[N << 2]; // 切记要开4 * n 的存储空间
pushup
1234inline void pushup(int u){ tr[u].sum = tr[lc].sum + tr[rc].sum;}
build
12345678910111213void build(int u, int l, int r){ tr[u] = {l, r, 0, 0}; if (l == r) { tr[u].sum = a[l]; return; } ...
【笔记/模板】拓扑排序
www.luogu.com.cn
拓扑排序
定义与实现思路
拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
根据定义可知，我们可以使用队列+BFS的方式求出一个图的拓扑序列，方法如下：
存图的时候记录下每个点的前驱数（即入度）。
从图中选择一个 没有前驱（即入度为 000）的顶点并输出，将其加入队列当中。
重复步骤 222 直到队列中的元素个数为 000 时，停止程序。
tips\bold tipstips：通常，一个有向无环图可以有一个或多个拓扑排序序列。
代码实现
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849// Problem: B3644 【模板】拓扑排序 / 家谱树// C ...
【笔记/模板】树状数组
原理解释
树状数组是一种通过前缀和和差分的思想所进行的维护数组，从而以 O(logn)O(\log n)O(logn) 的时间复杂度进行修改和查询。
一共有四种修改和查询的方式，分别是：
单点修改 +++ 区间询问
区间修改 +++ 单点询问
单点修改 +++ 区间询问
（二维）区间修改 +++ 区间询问
其中利用树状数组可以高效而简洁地处理第二、三个问题，第四个问题推荐使用【模板/笔记】线段树。
查询
查询可以计算左右区间的总和，通过它们的前缀和相减求出区间和。通过上图可以发现，如果要求 sum7sum_{7}sum7 的值，可以发现 sum7=tree7+tree6+tree4sum_{7} = tree_{7} + tree_{6} + tree_{4}sum7=tree7+tree6+tree4，而 7,6,47,6,47,6,4 之间有什么关联呢？
将其转化为二进制可以看出：7=(111)2,6=(110)2,4=(100)27=(111)_{2},6=(110)_{2},4=(100)_{2}7=(111)2,6=(110)2,4=(10 ...
【笔记/模板】ST表/RMQ
RMQ（区间最值问题）
Range Maxinum/Mininum Query（又称ST表）可以通过dp+倍增预处理的方式从而达到 O(nlogn)O(n \log n)O(nlogn) 的构建预处理，O(1)O(1)O(1) 的查询。
初始化
我们可以通过先定义一个二维数组 fi,jf_{i, j}fi,j表示从第 iii个数开始的区间大小为 jjj 的最值。而由于一个区间的最值 fi,jf_{i, j}fi,j 可以通过这个区间的两部分 fi,j−1和fi+2j−1,j−1f_{i, j - 1} 和 f_{i + 2 ^ {j - 1}, j - 1}fi,j−1和fi+2j−1,j−1得到，从而可以得到状态转移方程：
fi,j=max/min(fi,j−1,fi+2j−1,j−1)f_{i, j} = \max/\min(f_{i, j - 1}, f_{i + 2 ^{j - 1}, j - 1})
fi,j=max/min(fi,j−1,fi+2j−1,j−1)
数组的第一维范围为数据的最大范围 nnn，第二维为数据最大范围的 log2n\log_{2 ...
【笔记/模板】Johnson全源最短路
模板题目
www.luogu.com.cn
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114// Problem: P5905 【模板】全源最短路（Johnson）// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P5905// Memory Limit: 128 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>using namespace std;t ...
【笔记/模板】Dijkstra算法
原理解释
Dijkstra算法是通过贪心+BFS+动态规划实现的，可以用来计算单个点（源点）到其余任一点的距离大小。
Dijkstra算法的实现分为以下几步：
定义并初始化数组dis[N]，其中 disidis_{i}disi 表示源点当前距离 iii 点的最短距离，再定义一个 boolboolbool 数组 vis[N]， visivis_{i}visi 代表第 iii 个点是否被拓展过（即是否达到了最优解）。
从未被拓展的点中找出一个离源点最近的点 xxx（此时它已经是最优解），通过这个点依次松弛和它联通的每一个点距离源点的距离，同时将所松弛的点加入到队列当中。
等到队列中没有元素存在之后，结束函数，此时 dis[N] 中的每个点 disidis_{i}disi 即代表着距离源点的最小距离。
代码实现
朴素法
123struct Edge { int x, w; }; // x表示出点，w表示权值.vector<Edge> g[N]; //存图数组int dist[N]; //d[i]表示st距离i点的距离大小
12345678 ...
【笔记/模板】排序算法
【模板】快速排序 - 洛谷
1. 冒泡排序
排序原理：
每次将未确定部分的相邻两个值对比，设为ai,ai+1a_{i},a_{i+1}ai,ai+1，如果ai>ai+1a_{i}>a_{i+1}ai>ai+1,则对这两个值进行交换，可以使用swap来快速对两个值进行交换。
那么，这样一轮交换下去，第一个数就可以确定是最小的了。以此类推，直到所有值都被确定，就得出最终排好序的数列了。
时间复杂度：O(n2)O(n^2)
O(n2)
核心模板代码如下：
123456int n,a[100001];void pop_sort(){ for (int i = 1; i <= n; i ++) for (int j = 1; j < n;j ++) if (a[j] > a[j+1]) swap(a[j], a[j + 1]);//change a[j] and a[j+1].}
2. 桶排序
排序原理：
桶排序的原理很简单，就是定义一个数组为桶，然后每个桶代表一个数字，每输入一个数就将这个 ...
【笔记/模板】单调栈 单调队列
单调栈
定义
单调栈即满足单调性的栈结构。通过只在一端进出，从而维护一个数在前 / 后的第一个大于或小于它的数。
操作 / 方式
首先按照特定的顺序遍历。
如果要求出最小值，就要将栈顶大于入列元素的所有数全部弹出。
此时候的栈顶就是直到当前下标的答案。
加入这个元素并且继续更新。
代码
结构体 + STL模板
12345678910111213141516171819int a[N], ans[N];struct Node { int val, idx; };stack <Node> stk; signed main(){ // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = n; i >= 1; i--) { while (!stk.empty() & ...
【模板】Floyd算法以及扩展应用
Floyd 算法
原理
Floyd 算法用来求出任意两个节点之间的最短路。
优点：代码少，思维简单，适用于除了负环以外的任何图。
缺点：时间复杂度为 O(n3)O(n ^ 3)O(n3)，空间复杂度为 O(n2)O(n ^ 2)O(n2)。
而 Floyd 的核心原理是用动态规划实现的，定义一个二维数组 fi,jf_{i, j}fi,j，遍历图上的所有点 kkk，可以得到如下公式：
f[i][j]=min(f[i][j],f[i][k]+f[k][j])f[i][j] = min(f[i][j], f[i][k] + f[k][j])
f[i][j]=min(f[i][j],f[i][k]+f[k][j])
代码实现
1234for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
扩展应用
传递闭包
定义
给定一个不包含自环 ...