祝馀宫

算法简介：割舍怜悯之心最小生成树，就是一张图一直删边，直到删成一颗树为止，这叫做生成树，如果这个生成树的边权之和是所有生成树中最小的，那么他被称为最小生成树，前面我们讲过了一个叫做 Boruvka 的算法，虽然他确实是求最小生成树的方法之一，但是他过于远古，不太常用，代码也不如 kruskal 简单，所以说，我们这里将介绍两种新的最小生成树算法，请看副标题 —— Prim & kruskal 。 算法演示：割舍侥幸之心那么最小生成树，生成树生成树，总归就是树，有两种组成部分，一是点，二是边，而 Prim 和 kruskal 算法分别就是代表了基于点的贪心和基于边的贪心，我们来一个逐个击破。 点贪心：割舍痛苦之心首先就是 Prim 算法，他之所以被称为点贪心，是因为这样一个思路： 生成树，必须要把一个图的所有点连起来，变成一个树，也就是说，所有点，我们都将出现在最终的点集合里。所以，我们一开始随便选择一个点，加入最小生成树点集合，然后每次去寻找和我们最小生成树点集合最近的一个点，这样就可以保证每次选出来的边是最短的，然后就一直循环往复，直到所有点都选完。 然后，我们就发现，这样的 ...

算法简介：悬星尽散击云碎一般来讲，我们在大值域的权值线段树问题的时候，都会考虑把它变成离线的，然后进行线段树操作。但是，以万恶的出题人视角，一定会把这唯一的路给断掉，也就是强制在线的大值域权值线段树问题，那么我们就要考虑到动态开点权值线段树了。至于动态开点线段树的应用……想必都知道了吧 —— 线段树合并。 算法演示：璇玑合璧镇昆仑第一部分：星罗宿列天权临那么既然要讲的是动态开点权值线段树的应用，自然要讲动态开点权值线段树。那么我们首先来想，动态开点权值线段树的内存理论应该是多少。首先我们想权值线段树的内存，就和普通线段树一样，都是开了 $4N$ 的，那么如果是动态开点，显而易见我们就可以达到线段树的理论内存，$N\log V$ 其中，$N$ 是数据范围，$V$ 是值域。 有人可能想不通：我们都不知道数据里面最大的那个数，怎么开始数组，怎么建树，怎么往下递归寻找答案？ 上面这个有人是谁，我也不知道，但是有没有一种可能，我们是动态开点，我们不需要建树，我们的内存就是 $N\log V$ ，内存直接开到这么大就够了，也就是一般来讲的 N<<5 。这个 $5$ 的出处是 $2^ ...

算法简介：巡护深林KMP 算法，虽然我们已经在 【算法介绍】字符串算法 | 祝馀宫 中提及，但是现在有了更深的理解，我们这篇文章单独讲 KMP 算法以及其原理。为了凑字数，我们再讲一遍废话。 KMP 算法，全称 $Knuth-Morris-Pratt$ 算法，通过一种特殊的性质匹配两个字符串，从而达到减少匹配次数的算法。 算法演示：漫行山薮变量定义：夏堇芳菲我们对于接下来的一些内容做出如下定义： 名称 定义 子串 不用多说了罢，在字符串中截取任意一段连续的内容，被称为子串下文用 $s[l\dots r]$ 表示字符串 $s$ 的从 $l$ 到 $r$ 的这部分子串。 下文所有关于字符串的计算都是以 1 为开始的下标* 子序列 不要求连续，但是在原字符串中内容顺序相同的字符串。 前缀子串 一个字符串的前缀组成的子串，表示为 $pre(s,i)=s[1\dots i]$ ，即 $s$ 字符串长度为 $i$ 的前缀 后缀子串 一个字符串的后缀组成的子串，表示为 $suf(s, i) = s[n-i+1\dots n]$ ，即 $s$ 字符串长度为 $i$ 的后缀 ...

算法简介：正绢六通首先，说到矩阵乘法。字面意思的来讲，就是矩阵与矩阵之间的乘法，他们之间是否满足正常数字之间的乘法规则，也就是交换律与结合律呢？这部分的内容都将在下面被解释。 算法演示：落染五色矩阵加法：缀锦四分这个比较简单。首先我们了解一下矩阵的定义，对于一个 $n$ 行 $m$ 列的矩阵，我们有如下的表示方式： \left[\begin{matrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m} \end{matrix}\right]这样的矩阵，就是我们接下来的基础。首先讲到乘法，肯定会有人想到加法。但是实际上……矩阵的加法和乘法几乎一点关系都没有……但是提到了我们也顺便讲一下。 矩阵的运算不同于数字，两个矩阵之间是否可以进行运算，对于矩阵的行和列有着严格的规定。比如说加法，所对应的两个矩阵行和列必须一模一样，因为矩阵加 ...

算法简介：重帘留香树上莫队，就是字面意思上的树上的莫队，但实际上，一般来讲的树上莫队指的都是用欧拉序把一棵树压成数组，然后对其进行普通莫队的操作。 算法演示：天青现虹算法推导：织诗成锦那么首先我们可以随便画一棵树 然后我们首先手动算一算他的欧拉序。应该是 $[1,2,4,5,5,6,6,7,7,4,2,3,3,1]$ 。 那么我们考虑如果我们需要查询一个路径 $5-4-2-1-3$ ，会发生什么事。那么首先把他转化成欧拉序上的一段，也就是 5 的最后一次出现位置，和 3 的第一次出现位置，那么把它所对应的那一段截取下来就应该是：$[5,6,6,7,7,4,2,3$] ，观察，我们发现这个路径上的点，在这段内容中，多了 6 和 7 但是他们出现次数都是偶数，不难想到用异或或者 vis 去重可以得到，其次是 1 号点，1 号点是 LCA 我们应该需要特殊计算。所以说大概的找找规律，可以知道大概的计算方式。接着就是按照这样的规则模拟即可。 最后有一个细节问题，欧拉序的大小是原来的两倍！ 例题讲解：孤舟斩蛟这里提供一道非常非常模板的题目：SP10707 就是在上述板子的基础上统计一波颜色即可 ...