Posts

点分治和树剖有一个相同点，就是算法都是从暴力经过一小步优化而来，但就是这一小步，让算法复杂度有了质的飞跃。 下面来讲一下这个算法的原理。 概览 其实“点分治”也是一个名不副实的算法，看完下面的讲述你就会发现这个算法根“分治”几乎无关。 点分治是专门解决树上路径统计的一种算法（树剖则是解决对树上路径的判断的算法）。 点分治的思想很朴素，就是DFS一下 $\text{lca}$ 的节点编号 $x$，然后统计 $\text{lca}$ 值刚好为 $x$ 的、满足题目条件的路径的数量，并累加到答案。 但直接进行统计还是炸裂的，点分治则是对这种统计方式做了一步优化 解决题型 上面说了，「点分治是专门解决树上路径统计的一种算法」，但并不是所有的树上路径统计都可以用点分治解决。 其实看完下面的实现，你就能知道它解决什么类问题，不过这里还是说一下。 就是首先，这个条件是形如“总和比某个值低”、“总和是某个值的倍数”等“可累加”的条件。 其中“可累加”指的是，如果知道了 $A$ 部分的某个值，和 $B$ 部分的某个值，那么 $A$ 和 $B$ 部分合并后的部分是否合法也一定知道。 但其他的条件目前还没有太明确，得自己去总结。 算法实现 下面说一下点分治的实现。 大体思路 我们拿“路径长度（路径上的边的边权之和）刚好为 $k$”问题举例。 注：原题链接P3806 就是我们考虑，当DFS到某个点 $x$ 的时候，就如上所说，设 $x$ 为 $\text{lca}$ 值。 然后，我们按顺序遍历所有子节点 $to$。 由于只要两个点 $y$、$z$ 满足 $y$ 和 $z$ 分别在 $x$ 的两个不同儿子及其子树内，那么 $\text{lca}(y,z)=x$。 并且所有满足条件 $\text{lca}(y,z)=x$ 的对 $(y,z)$ 只有满足上述条件的对。 所以，我们可以通过（另一种）DFS（方式）求出 $to$ 到 ( 所有 $to$ 及其子树内的点 ) 之间的距离（加上 $x \to to$ 的边权）的集合 $T$。 ...

基尔霍夫矩阵是用来求解生成树计数、求（权值）和相关题目的利器。 0. 求完全图的生成树数量（Prufer序列） 要说基尔霍夫矩阵，就要从一道题目说起： 给你 $n$，问 $n$ 个节点组成的无向无根树有多少种。 这道题可以用Prufer序列去做。 这里简单说一下Prufer序列的求法： 对于一张无向无根树，重复执行以下操作直到只剩 $2$ 个或更少的点，最后得到的那个序列 $a$ 就是这棵树的Prufer序列： 我们找到此时度为 $1$ 的节点，若有多个，找编号最小的，设找到的节点编号为 $x$。 在 $a$ 的末尾添加：与 $x$ 有连边的那个唯一节点。 删除 $x$。 Prufer序列别看求法非常简单，也没啥容易发现的性质，其实用处很大。 Prufer序列满足一个性质，就是，所有无向无根树，都可以唯一地对应一个Prufer序列；所有Prufer序列都可以唯一地对应一棵树。 所以，这道题就有解了，答案其实就是长为 $n-2$ 的Prufer序列有多少种。 由于Prufer序列的每个元素的值都是从 $1$ 到 $n$ 的，所以答案就是 $n^{n-2}$，显然。 1.1. 求任意无向图的生成树数量（基尔霍夫矩阵） 但如果把题目变化一下，就不能用Prufer序列去求了： 给你一张 $n$ 个节点 $m$ 条边的无向图，问这张图的生成树有多少个。 这题要用基尔霍夫矩阵。 具体地，我们定义 $D$ 矩阵，求法： $ D_{i,j}= \begin{cases} 0 & i \not= j \ \text{deg}(i) & i=j \end{cases} $ 其中，$\text{deg}(i)$ 代表这张图上 $i$ 的度是多少。 ...

二维决策单调性 对于形如 $d_{i,j}=\min\limits_{k=0}^{i-1} \Big( d_{k,j-1}+w(k+1,i) \Big)$ 的方程，我们尝试记录 $f_{i,j}$ 代表 $d_{i,j}$ 的最优转移点（$k$ 变量），如果有 $f_{i,j-1} \leq f_{i,j} \leq f_{i+1,j}$，那么就是经典的四边形不等式优化，复杂度为 $O(n^2)$，证明此处略（在"四边形不等式相关.md"里有）。 但是，如果只有 $f_{i,j} \leq f_{i+1,j}$，那么就不能用四边形不等式优化了，需要用分治的方式优化。 具体地，我们从小到大枚举 $j$，然后转移所有的 $d_{i,j}$。 定义分治函数dp(l,r,jl,jr)代表我们要转移所有的 $d_{i,j}$（$l \leq i \leq r$），并且保证所有在本次分治转移范围内的 $d_{i,j}$ 的转移点 $f_{i,j}$ 都在 $[jl,jr]$ 内。 我们可以先求出 $[l,r]$ 的中点 $mid$，然后转移 $d_{mid,j}$：暴力枚举转移点 $k$（当然，要在 $[jl,jr]$ 内）进行转移，并递归dp(l,mid-1,jl,最终转移点)和dp(mid+1,r,最终转移点,jr)。 该算法复杂度为 $O(n^2 \log n)$，证明： 首先，枚举 $j$ 的复杂度 $O(n)$。 其次，只看 $[jl,jr]$，$[jl,jr]$ 在递归的过程中就形成了个线段树的类似结构，只不过单层内可能有部分重叠位置，而且划分点（上面说的“最终转移点”）可能不是中点，不过无关紧要。 然后，再看 $[l,r]$，$[l,r]$ 在递归过程中也形成了类似于线段树的结构，并且易证这个递归树深度是不会超过 $\log n$ 的。 有了深度的保证，而且一层内的 $[jl,jr]$ 区间长度和最多只有 $O(n)$ 级别，所以一次分治的复杂度就是 $O(n \log n)$。 ...

来源：ABC372G官方题解 贡献：OI Wiki 这个算法确实挺妙的，所以我就写个笔记。 定义 这个算法需要用到一个函数： $$ f(a,b,c,n)=\sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a\color{default}i+\color{blue}b\color{default}}{\color{green}c\color{default}} \right\rfloor $$ 在下面参数 $a$、$b$、$c$ 都会用三种颜色标出，以便于区分。 因为 $a$、$b$、$c$、$n$ 都很大，所以我们没法直接暴力求。 数论分块显然也不彳亍。 所以我们只能另辟蹊径了。 求值 咱从简单到复杂走。 1 首先，我们可以知道： $$ \begin{aligned} f(a,b,c,n)&=\sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a\color{default}i+\color{blue}b\color{default}}{\color{green}c\color{default}} \right\rfloor \ &=\sum\limits_{i=0}^n \left\lfloor \dfrac{(\lfloor \frac{a}{c} \rfloor c + a \bmod c)i+(\lfloor \frac{b}{c} \rfloor c + b \bmod c)}{c} \right\rfloor \ &=\sum\limits_{i=0}^n \left\lfloor \dfrac{\lfloor \frac{a}{c} \rfloor c \cdot i + a \bmod c \cdot i+\lfloor \frac{b}{c} \rfloor c + b \bmod c}{c} \right\rfloor \ &=\sum\limits_{i=0}^n \left( \left\lfloor \frac{a}{c} \right\rfloor i + \left\lfloor \frac{b}{c} \right\rfloor + \left\lfloor \dfrac{a \bmod c \cdot i+b \bmod c}{c} \right\rfloor \right) \ &=\dfrac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + (n+1) \left\lfloor \frac{b}{c} \right\rfloor + \sum\limits_{i=0}^n \left\lfloor \dfrac{\color{red}a \bmod c\color{default} \cdot i+\color{blue}b \bmod c\color{default}}{\color{green}c\color{default}} \right\rfloor \ &=\dfrac{n(n+1)}{2} \left\lfloor \frac{a}{c} \right\rfloor + (n+1) \left\lfloor \frac{b}{c} \right\rfloor + f(a \bmod c,b \bmod c,c,n) \ \end{aligned} $$ ...

马拉车算法其实就是解决一个字符串中由某个位置为中心的最大回文串长度：（下图中蓝色部分为字符串，绿色框中的值就是以这个位置为中心的最大回文串长度） 其次，我们发现最底下的一排绿色数字涉及到空隙，所以我们可以把字符串扩展一下： 比如，原字符串是 $\texttt{abccabbc}$，那么扩展之后就是： （LaTeX炸了） $\texttt{\color{RoyalBlue}@\color{default}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{RoyalBlue}&}$ 第一个和最后一个字符可以自己定，但是最好不要和原字符串中的字符、中间插入的字符冲突（相等）。 注：其实还有第二种扩展方法： $\texttt{\color{RoyalBlue}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}a\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}b\color{RoyalBlue}#\color{default}c\color{RoyalBlue}#\color{default}}$ 还是，中间字符不能与原串字符相等。 下面统一设「以下标 $i$ 为中心的最大回文串长度除以 $2$ 并下取整」后的答案为 $p_i$。 然后，我们就开始求 $p$ 数组了，当我们求到 $p_i$ 的时候，我们看前面求出的 $p_j+j$ 的最大值是多少（设为 $r$），即 $\max\limits_{j=1}^{i-1} { p_j+j }$，同时求出最大的 $p_j+j$ 对应的 $j$（设为 $c$）。 并且，我们求出 $i$ 的对称点 $i’$，对称中心为 $c$，显然 $i’=2c-i$。 然后，分类讨论： 注：图中 $r$ 的意思与上面说的 $r$ 的意思有冲突，统一以上面说的定义为准。 $i>r$，那么暴力算 $p_i$。 $r-i \geq p_{i’}$，那么 $p_i=p_{i’}$。 $r-i<p_{i’}$，那么让 $p_i=r-i$，继续暴力扩展。 最后就是时间复杂度问题了。 关于时间复杂度的证明，我们可以分类讨论 $p_i$ 是用那种情况求值的： 用情况1转移：$r$ 肯定会增加。 用情况2转移：复杂度忽略。 用情况3转移：$r$ 也肯定会增加。 由于每时每刻，$r$ 都小于等于 $n$，所以总复杂度就是 $O(n)$ 的。 ...

欧拉函数记为 $\varphi$，$\varphi(n)$ 代表 $1 \sim n$ 内与 $n$ 互质的数的个数。 欧拉函数有两种求法，下面分别说： 直接求 我们设 $p$ 为 $n$ 的质因子集合（非可重集），那么 $\varphi(n)=n \times \prod\limits_{x \in p} \left( \dfrac{x-1}{x} \right)$，原理： 我们设 $s$ 为目前与 $n$ 互质的数的集合，初始为 ${ 1,2,\dots,n }$。 每次遍历到一个 $p$ 中的数 $x$，就会筛掉这个集合中 $\dfrac{1}{x}$ 的数，即那些是 $x$ 的倍数的数，由于 $p$ 是去重后的质因子集合，所以当前集合的大小总是 $x$ 的倍数。 所以这个做法就能证明了，每乘一次 $\dfrac{x-1}{x}$，都相当于筛掉当前集合内 $\dfrac{1}{x}$ 的数，集合大小动态维护。 模板代码：（代码中的 $p$ 数组是提前筛出来的质数集合，$ind$ 为其大小） LL phi(LL n){ if(n == 0) return 0; LL ret = n; rep(i, 1, ind){ if(n % p[i] == 0) ret = ret * 1 - ret / p[i], n /= p[i]; while(n % p[i] == 0) n /= p[i]; } if(n > 1) ret = ret * 1 - ret / n; return ret; } 通过线性筛预处理 线性筛模板： void shai(LL n){ f[0] = f[1] = true; rep(i, 2, n){ if(!f[i]) p[++ind] = i; for(LL j = 1;i * p[j] <= n;j++){ f[i * p[j]] = true; if(i % p[j] == 0) break; } } } 线性筛有一个性质，就是在第二重循环里，每次都会筛掉数 $i \times p_j$，而 $p_j$ 正是这个数（$i \times p_j$）的最小质因子。 ...

我们现在要解决一个问题，就如标题所说，我们要判断一个DAG的拓扑序是否唯一。 以下说两种做法。 做法1（推荐） 在拓扑排序时，我们只要每时每刻都判断一下，此时的队列大小是否大于 $1$ 即可。 因为，如果队列大小大于 $1$，则选择任何一个元素都可以加入到拓扑序的最后下标，所以拓扑序不唯一。 做法2 （以下是我考试时想出来的做法，思维难度较高，但整个构思过程中都没有思维跳跃） 1 首先，我们建出这个DAG，然后我们考虑，其实一个DAG唯一，有且仅当对于所有点对 $(u,v)$（$1 \leq u,v \leq n$），都满足以下两点之一： 点 $u$ 可以到达点 $v$。 点 $v$ 可以到达点 $u$。 此处证明一下。 其实，如果存在一个不满足上述条件的点对 $(u,v)$，那么整张图可能会张这样：（下面标记的 $(u,v)$ 只是其中一个） 在这种情况里，我们直接把红色集合和蓝色集合里的拓扑序“交换”，变成： 于是乎，就得到了另一个合法的拓扑序，证毕。 关于如果满足条件，则拓扑序唯一，此处不多赘述，自行脑补。 2 上述条件还可以继续变化，变成： 对于所有点对 $(u,v)$（$1 \leq u,v \leq n$，且 $v$ 的拓扑序比 $u$ 的要大），都满足点 $u$ 可以到达点 $v$。 3 我们考虑定义函数 $f(x)$ 代表拓扑序为 $x$ 的节点，是否能到达所有拓扑序为 $y$（$x<y$）的点。 4 我们考虑求 $f(x)$，我们可以枚举拓扑序为 $x$ 的节点 $u$ 的所有出点 $v$（设其拓扑序为 $y$，且排除 $y \leq x$ 的所有点）。 ...

说到平衡树，很多人的第一印象就是： 难学（知识点真多） 难懂（特别是“旋转”和证明） 难调（我的某个教练刚学平衡树的时候调了七个小时） 下面我们就来从0开始讲平衡树。 （注：网上大多数人说到“平衡树”默认指的是“Splay”而不是其他算法） 定义 其实平衡树（Balance Tree，简称BT）不算一种算法，而是一种统称。 平衡树顾名思义就是非常平衡的树。 比如说这棵树就非常不平衡： 而这棵树就比较平衡： 如果说的更形式化，平衡就意味着，对于每个点，其所有子树的大小差都不超过 $1$。 具体而言，对于每个点 $x$，如果我们把其所有儿子 $to$ 的子树大小都列出来，那么这个数组内最大值和最小值差不超过 $1$。 而且，大多数平衡树都是二叉树，这一点是为了方便操作和设计算法。 种类 听完上面的定义，你就知道了，平衡树就是一类树状数据结构的统称。 下面就来列举一下这类数据结构都有哪些，以及这些数据结构的简介。 二叉搜索树（Binary Search Tree，简称BST） 大多数平衡树的前置算法，这也就意味着，大多数的平衡树都是基于BST并进行优化、扩展后得到的算法。 而BST也是线段树（Segment Tree，部分情况下会简称为ST）进行扩展后的算法。 具体而言，权值线段树和BST都可以维护有序集合，但有时候只能用BST解决。 BST其实就是把权值“当做”节点编号（讲的时候一般就这么讲，但写的时候不能这么写，是把权值存入该节点的结构体内）。 然后对于每个点，它都有最多 $2$ 个儿子，左儿子权值 $<$ 当前点权值 $<$ 右儿子权值。 这样就可以方便查找。 优点：代码好写，容易讲明白 缺点：解决题型少，需要写定期重构（又被称作“替罪羊树思想”），复杂度高 Treap（名字不是一个单词，而是两个单词Tree和Heap的结合） 这个算法给每个节点都添加了一个“优先级”，并让“优先级”满足小/大根堆的性质。 并且，这里还通过“旋转”操作（最头疼的地方来了）让树尽量平衡，这样会让树高稳定在 $O(\log n)$ 级别。 （不过注意，在最坏情况下，复杂度会达到 $O(n)$，所以 $O(\log n)$ 只是期望） 这样，复杂度就降下来了。 优点：复杂度低，比较容易理解，解决题型多，且容易被识别出 缺点：比较难写，细节较多，复杂度难证明 Splay（本意为“张开”但这里不是这个意思） 这个算法对上面的“旋转”操作又做了一遍扩展，让其能够解决子串翻转问题。 而且，由于它也会让整棵树尽量平衡，所以树高还是会稳定在 $O(\log n)$ 级别。 ...

参考 引用头文件（常用） #include <stdlib.h> //生成随机数、设定随机数种子 #include <ctime> //生成随机数种子（1） #include <time.h> //生成随机数种子（2） #include <unistd.h> //等待（sleep(...)或usleep(...)），该头文件现在不常用 随机种子 srand(time(0) ^ clock()); 注：随机种子为time(0) ^ clock()，这个随机种子可以再毫秒级别内生成（大概率）不同的随机种子。 取 $[l,r]$ 内的随机数 #define random(l, r) (rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l)) 注：rand函数只能生成 $[1,32767]$ 内的随机数（见宏RAND_MAX），大概只能生成位数 $\leq 5$ 的随机数；测试程序： LL ma = 0; for(LL i = 1;i <= 200;i++){ srand(time(0) ^ clock()); LL t = rand(); cout << t <<endl; ma = max(ma, t); usleep(10000); } cout << ma <<endl; 所以此处引用一个新方法：mt19937（2022/12/24：现在开始使用mt19937_64了，它可以生成 $[1,2^{64})$ 内的随机数，大一倍）。 其实它的语法和rand的语法差不多 （才怪），是这样的： 引用头文件（常用） #include <random> //生成随机数、设定随机数种子 #include <ctime> //生成随机数种子（1） #include <time.h> //生成随机数种子（2） #include <unistd.h> //等待（sleep(...)或usleep(...)），该头文件现在不常用 随机种子 mt19937 _rand(time(0) ^ clock()); 注：这个随机种子也可以再毫秒级别内生成（大概率）不同的随机种子 取 $[l,r]$ 内的随机数 （就差一个字符_而已） #define random(l, r) (_rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l)) 据测试，这个函数可以生成在unsigned int范围内的随机数（即可以生成 $[1,2^{32})$ 内的随机数），测试程序： ...

第一次看到树链剖分（简称树剖）可能觉得它非常的深奥，但其实树剖的原理非常简单，下面先说树剖大概的实现思路和解决题型。 概览 其实树剖就是把一棵树分成若干条链，使得每个点都出现在了刚好一条链上。 并且，我们称在某条链上的边为“重（zhòng）边”，不在任何一条链上的边为“轻边”。 然后，我们按某种规则去DFS，求出新的DFS序，然后解决对树上路径询问的问题。 而且，通过合理的设计每条边的轻重，可以把复杂度控制在 $O(\log n)$ 级别。 解决题型 上面也提到了，树剖就是用来解决对树上路径进行询问的问题的算法，当然也可以解决对子树询问的问题，不过属于大材小用了。 此外，树剖属于工具类算法，所以往往会配合树状数组、线段树、分块等算法出现。 我把算法分为了两类，“材料类算法”和“工具类算法”，其中： 材料类算法可以单独考，比如： 数论 推公式 DP 树状数组 线段树 … 工具类算法里面必须要套材料类算法才能考出来，比如： 二分 01分数规划（二分的一个分支） CDQ分治（需要配合树状数组） 整体二分（需要配合树状数组） 树剖（这里讲的） … 往往一些较难的题目，都是要用较难的材料类算法（比如DP），或者工具类算法配合材料类算法才能解决的题目。 而对于后者，难度会更大一些，因为后者的关键在于转化后使用工具类算法解决。 算法实现 下面说一下树剖的实现。 两遍DFS 我们考虑DFS，当递归到点 $x$ 的时候，找到 $x$ 的儿子中，子树大小最大的那个儿子 $to$。 然后，我们把 $x \to to$ 这条边设为重边，其他边设为轻边。 得到每条边的轻重后，我们再做一遍DFS。 而这一遍DFS是为了找到DFS序。 而且，DFS序有一个要求，我们要先遍历有重边连接的儿子。 这样的话，对于任意一条树上的链，链上所有点的DFS序连续，而且是由深度从浅到深依次递增。 同时，我们还要求出，从一个点开始，不经过任何轻边，最多到哪个点。 解决询问 而对于一次路径上某值的询问，我们可以把这个路径拆成若干条链。 可以证明链数不超过 $O(\log n)$，这一点会在下面“复杂度证明”中证明。 而这些拆出的链，都是原树中的链的“子集”（一条链 $L_1$ 是另外一条链 $L_2$ 的子集，有且仅当 $L_1$ 中的点，$L_2$ 中也有，边同理）。 所以，可以把一条路径，拆成最多 $O(\log n)$ 个DFS序区间。 ...