From bb0f4669a4537efa5cdf30cdc53377322aa14304 Mon Sep 17 00:00:00 2001
From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com>
Date: Thu, 22 Oct 2020 09:04:36 -0400
Subject: [PATCH] style: format markdown files with remark-lint

---
 docs/math/sieve.md    |  2 +-
 docs/topic/dsu-app.md | 46 +++++++++++++++++++++++-----------------------
 2 files changed, 24 insertions(+), 24 deletions(-)

diff --git a/docs/math/sieve.md b/docs/math/sieve.md
index c43daea1..1458ca81 100644
--- a/docs/math/sieve.md
+++ b/docs/math/sieve.md
@@ -309,4 +309,4 @@ void pre() {
 
 ## 其他线性函数
 
-**本节部分内容译自博文 [Решето Эратосфена](http://e-maxx.ru/algo/eratosthenes_sieve) 与其英文翻译版 [Sieve of Eratosthenes](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html) 。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。** 
+ **本节部分内容译自博文 [Решето Эратосфена](http://e-maxx.ru/algo/eratosthenes_sieve) 与其英文翻译版 [Sieve of Eratosthenes](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html) 。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。** 
diff --git a/docs/topic/dsu-app.md b/docs/topic/dsu-app.md
index cfe198fc..f6af1a04 100644
--- a/docs/topic/dsu-app.md
+++ b/docs/topic/dsu-app.md
@@ -11,7 +11,7 @@ author: sshwy
     
     在 $m$ 次操作完后，你要求出 $\sum_{i=1}^n\sum_{j=i+1}^nL(i,j)$ 的值。
 
-这是基础并查集的应用，并查集记录一下子树的大小。考虑统计每次操作的贡献。如果第 $i$ 次操作 $a_i$ 和 $b_i$ 分属于两个不同子树，就将这两个子树合并，并将两者子树大小的乘积乘上 $i$ 累加到答案里。时间复杂度 $O(n\alpha(n))$。
+这是基础并查集的应用，并查集记录一下子树的大小。考虑统计每次操作的贡献。如果第 $i$ 次操作 $a_i$ 和 $b_i$ 分属于两个不同子树，就将这两个子树合并，并将两者子树大小的乘积乘上 $i$ 累加到答案里。时间复杂度 $O(n\alpha(n))$ 。
 
 ## B
 
@@ -22,47 +22,47 @@ author: sshwy
     
     接下来有 $q$ 次询问，第 $i$ 次询问 $u_i$ 和 $v_i$ 最早在第几次操作后连通。
 
-考虑在并查集合并的时候记录「并查集生成树」，也就是说如果第 $i$ 次操作 $a_i$ 和 $b_i$ 分属于两个不同子树，那么把 $(a_i,b_i)$ 这条边纳入生成树中。边权是 $i$。那么查询就是询问 $u$ 到 $v$ 路径上边权的最大值，可以使用树上倍增或者树链剖分的方法维护。时间复杂度 $O(n\log_2n)$。
+考虑在并查集合并的时候记录「并查集生成树」，也就是说如果第 $i$ 次操作 $a_i$ 和 $b_i$ 分属于两个不同子树，那么把 $(a_i,b_i)$ 这条边纳入生成树中。边权是 $i$ 。那么查询就是询问 $u$ 到 $v$ 路径上边权的最大值，可以使用树上倍增或者树链剖分的方法维护。时间复杂度 $O(n\log_2n)$ 。
 
-另外一个方法是维护Kruskal重构树，其本质与并查集生成树是相同的。复杂度亦相同。
+另外一个方法是维护 Kruskal 重构树，其本质与并查集生成树是相同的。复杂度亦相同。
 
 ## C
 
-???+note “C”
+???+note“C”
     有 $n$ 个点，初始时均为孤立点。
-    
+
     接下来有 $m$ 次加边操作，第 $i$ 次操作在 $a_i$ 和 $b_i$ 之间加一条无向边。
-    
+
     接下来有 $q$ 次询问，第 $i$ 次询问第 $x_i$ 个点在第 $t_i$ 次操作后所在连通块的大小。
 
-离线算法：考虑将询问按 $t_i$ 从小到大排序。在加边的过程中顺便处理询问即可。时间复杂度 $O(q\log_2q+(n+q)\alpha(n))$。
+离线算法：考虑将询问按 $t_i$ 从小到大排序。在加边的过程中顺便处理询问即可。时间复杂度 $O(q\log_2q+(n+q)\alpha(n))$ 。
 
-在线算法：本题的在线算法只能使用Kruskal重构树。Kruskal重构树与并查集的区别是：第 $i$ 次操作 $a_i$ 和 $b_i$ 分属于两个不同子树，那么Kruskal会新建一个结点 $u$ ，然后让 $a_i$ 所在子树的根和 $b_i$ 所在子树的根分别连向 $u$，作为 $u$ 的两个儿子。不妨设 $u$ 的点权是 $i$。对于初始的 $n$ 个点，点权为 $0$。
+在线算法：本题的在线算法只能使用 Kruskal 重构树。Kruskal 重构树与并查集的区别是：第 $i$ 次操作 $a_i$ 和 $b_i$ 分属于两个不同子树，那么 Kruskal 会新建一个结点 $u$ ，然后让 $a_i$ 所在子树的根和 $b_i$ 所在子树的根分别连向 $u$ ，作为 $u$ 的两个儿子。不妨设 $u$ 的点权是 $i$ 。对于初始的 $n$ 个点，点权为 $0$ 。
 
-对于询问，我们只需要求出 $x_i$ 在重构树中最大的一个连通块使得连通中的点权最大值不超过 $t_i$，询问的答案就是这个连通块中点权为 $0$ 的结点个数，即叶子结点个数。
+对于询问，我们只需要求出 $x_i$ 在重构树中最大的一个连通块使得连通中的点权最大值不超过 $t_i$ ，询问的答案就是这个连通块中点权为 $0$ 的结点个数，即叶子结点个数。
 
-由于我们操作的编号是递增的，因此重构树上父结点的点权总是大于子结点的点权。这意味着我们可以在重构树上从 $x_i$ 到根结点的路径上倍增找到点权最大的不超过 $t_i$ 的结点。这样我们就求出了答案。时间复杂度 $O(n\log_2n)$。
+由于我们操作的编号是递增的，因此重构树上父结点的点权总是大于子结点的点权。这意味着我们可以在重构树上从 $x_i$ 到根结点的路径上倍增找到点权最大的不超过 $t_i$ 的结点。这样我们就求出了答案。时间复杂度 $O(n\log_2n)$ 。
 
 ## D
 
 ???+note "D"
-    给一个长度为 $n$ 的01序列 $a_1,\ldots,a_n$，一开始全是 $0$，接下来进行 $m$ 次操作：
+    给一个长度为 $n$ 的 01 序列 $a_1,\ldots,a_n$ ，一开始全是 $0$ ，接下来进行 $m$ 次操作：
     
-    - 令 $a_x=1$；
+    - 令 $a_x=1$ ；
     - 求 $a_x,a_{x+1},\ldots,a_n$ 中左数第一个为 $0$ 的位置。
 
-建立一个并查集，$f_i$ 表示 $a_i,a_{i+1},\ldots,a_n$ 中第一个 $0$ 的位置。初始时 $f_i=i$。
+建立一个并查集， $f_i$ 表示 $a_i,a_{i+1},\ldots,a_n$ 中第一个 $0$ 的位置。初始时 $f_i=i$ 。
 
-对于一次 $a_x=1$ 的操作，如果 $a_x$ 原本就等于 $1$，就不管。否则我们令 $f_x=f_{x+1}$。
+对于一次 $a_x=1$ 的操作，如果 $a_x$ 原本就等于 $1$ ，就不管。否则我们令 $f_x=f_{x+1}$ 。
 
-时间复杂度 $O(n\log_2n)$，如果要使用按秩合并的话实现会较为麻烦，不过仍然可行。也就是说时间复杂度或为 $O(n\alpha(n))$。
+时间复杂度 $O(n\log_2n)$ ，如果要使用按秩合并的话实现会较为麻烦，不过仍然可行。也就是说时间复杂度或为 $O(n\alpha(n))$ 。
 
 ## E
 
 ???+note "E"
-    给出三个长度为 $n$ 的正整数序列 $a$，$b$，$c$。枚举 $1\le i\le j\le n$，求 $a_i\cdot b_j\cdot \min_{i\le k\le j}c_k$ 的最大值。
+    给出三个长度为 $n$ 的正整数序列 $a$ ， $b$ ， $c$ 。枚举 $1\le i\le j\le n$ ，求 $a_i\cdot b_j\cdot \min_{i\le k\le j}c_k$ 的最大值。
 
-本题同样有许多做法，这里我们重点讲解并查集思路。按权值从大到小考虑 $c_k$。相当于我们在 $k$ 上加入一个点，然后将 $k-1$ 和 $k+1$ 位置上的点所在的连通块与之合并（如果这两个位置上有点的话）。连通块上记录 $a$ 的最大值和 $b$ 的最大值，即可在合并的时候更新答案。时间复杂度 $O(n\log_2n)$。
+本题同样有许多做法，这里我们重点讲解并查集思路。按权值从大到小考虑 $c_k$ 。相当于我们在 $k$ 上加入一个点，然后将 $k-1$ 和 $k+1$ 位置上的点所在的连通块与之合并（如果这两个位置上有点的话）。连通块上记录 $a$ 的最大值和 $b$ 的最大值，即可在合并的时候更新答案。时间复杂度 $O(n\log_2n)$ 。
 
 ## F
 
@@ -76,7 +76,7 @@ author: sshwy
 
 换言之，加边操作可以理解为，将 $a_i$ 到 $b_i$ 树上路径的边覆盖一次。而询问就转化为了：判断 $u_i$ 到 $v_i$ 路径上是否存在未被覆盖的边。如果不存在，那么 $u_i$ 和 $v_i$ 就属于同一个双连通分量，也就属于同一个简单环。
 
-考虑使用并查集维护。给树定根，设 $f_i$ 表示 $i$ 到根的路径中第一个未被覆盖的边。那么每次加边操作，我们就暴力跳并查集。覆盖了一条边后，将这条边对应结点的 $f$ 与父节点合并。这样，每条边至多被覆盖一次，总复杂度 $O(n\log_2n)$。使用按秩合并的并查集同样可以做到 $O(n\alpha(n))$。
+考虑使用并查集维护。给树定根，设 $f_i$ 表示 $i$ 到根的路径中第一个未被覆盖的边。那么每次加边操作，我们就暴力跳并查集。覆盖了一条边后，将这条边对应结点的 $f$ 与父节点合并。这样，每条边至多被覆盖一次，总复杂度 $O(n\log_2n)$ 。使用按秩合并的并查集同样可以做到 $O(n\alpha(n))$ 。
 
 本题的维护方式类似于 D 的树上版本。
 
@@ -89,20 +89,20 @@ author: sshwy
     
     每次操作后，你均需要求出图中桥的个数。
     
-    桥的定义为：对于一条 $G$ 中的边 $(x,y)$，如果删掉它会使得连通块数量增加，则 $(x,y)$ 被称作桥。
+    桥的定义为：对于一条 $G$ 中的边 $(x,y)$ ，如果删掉它会使得连通块数量增加，则 $(x,y)$ 被称作桥。
     
     强制在线。
 
 本题考察对并查集性质的理解。考虑用并查集维护连通情况。对于边双树，考虑维护有根树，设 $p_i$ 表示结点 $i$ 的父亲。也就是不带路径压缩的并查集。
 
-如果第 $i$ 次操作 $a_i$ 和 $b_i$ 属于同一个连通块，那么我们就需要将边双树上 $a_i$ 到 $b_i$ 路径上的点缩起来。这可以用并查集维护。每次缩点，边双连通分量的个数减少 $1$，最多减少 $n-1$ 次，因此缩点部分的并查集复杂度是 $O(n\alpha(n))$。
+如果第 $i$ 次操作 $a_i$ 和 $b_i$ 属于同一个连通块，那么我们就需要将边双树上 $a_i$ 到 $b_i$ 路径上的点缩起来。这可以用并查集维护。每次缩点，边双连通分量的个数减少 $1$ ，最多减少 $n-1$ 次，因此缩点部分的并查集复杂度是 $O(n\alpha(n))$ 。
 
-为了缩点，我们要先求出 $a_i$ 和 $b_i$ 在边双树上的LCA。对此我们可以维护一个标记数组。然后从 $a_i$ 和 $b_i$ 开始轮流沿着祖先一个一个往上跳，并标记沿途经过的点。一但跳到了某个之前就被标记过的点，那么这个点就是 $a_i$ 和 $b_i$ 的LCA。这个算法的复杂度与 $a_i$ 到 $b_i$ 的路径长度是线性相关的，可以接受。
+为了缩点，我们要先求出 $a_i$ 和 $b_i$ 在边双树上的 LCA。对此我们可以维护一个标记数组。然后从 $a_i$ 和 $b_i$ 开始轮流沿着祖先一个一个往上跳，并标记沿途经过的点。一但跳到了某个之前就被标记过的点，那么这个点就是 $a_i$ 和 $b_i$ 的 LCA。这个算法的复杂度与 $a_i$ 到 $b_i$ 的路径长度是线性相关的，可以接受。
 
-如果 $a_i$ 和 $b_i$ 分属于两个不同连通块，那么我们将这两个连通块合并，并且桥的数量加 $1$。此时我们需要将两个点所在的边双树连起来，也就是加一条 $a_i$ 到 $b_i$ 的边。因此我们需要将其中一棵树重新定根，然后接到另一棵树上。这里运用启发式合并的思想：我们把结点数更小的重新定根。这样的总复杂度是 $O(n\log n)$ 的。
+如果 $a_i$ 和 $b_i$ 分属于两个不同连通块，那么我们将这两个连通块合并，并且桥的数量加 $1$ 。此时我们需要将两个点所在的边双树连起来，也就是加一条 $a_i$ 到 $b_i$ 的边。因此我们需要将其中一棵树重新定根，然后接到另一棵树上。这里运用启发式合并的思想：我们把结点数更小的重新定根。这样的总复杂度是 $O(n\log n)$ 的。
 
 综上，该算法的总复杂度是 $O(n\log_2n+m\log_2n)$ 的。
 
 ## 小结
 
-并查集与Kruskal重构树有许多共通点，而并查集的优化（按秩合并）正是启发式合并思想的应用。因此灵活运用并查集可以方便地处理许多与连通性有关的图论问题。
+并查集与 Kruskal 重构树有许多共通点，而并查集的优化（按秩合并）正是启发式合并思想的应用。因此灵活运用并查集可以方便地处理许多与连通性有关的图论问题。
-- 
2.11.0