玄学算法/精彩DS总结 Miloring

## $46.Suffix\ Array$ 后缀数组是处理字符串的有力工具。~~是不是在哪听过~~ 它看似没有$SAM$的功能强大，实际上它有某些特殊的用途是$SAM$不可替代的。~~当然这主要是后缀数组的副产物~~ 如无特殊情况，下文字符串的偏序关系都是字典序。 ### $Properties:$ ### $sa$ 字面意思，$sa(i)$表示排名为$i$的后缀的起始位置下标。也就是后缀数组算法直接要求的东西。与$rank(i)$成相互映射的关系。 ### $rank$ 字面意思，$rank(i)$表示起始位置下标为$i$的后缀（下称$suf(i)$）的排名。也就是后缀数组算法直接求出的东西。与$sa(i)$成相互映射的关系。 ### $LCP$ $LCP(i,j)$指的是$suf(sa[i]),suf(sa[j])$的最长公共前缀。这是$SA$相当重要的副产物。显然$LCP(i,i)=n-sa[i]+1$，所以我们只需要求解$i<j$的部分。 $LCP\ Theorem:$ $$LCP(i,j)=\min(\sum_{k=i+1}^jLCP(k-1,k))$$ 感觉上比较显然。严谨证明的话说不定可以用数学归纳法？ 感性证明的话，$LCP$既然是前缀的相同部分，那么$i,j$之间的那些相邻后缀中**永恒不变的共同部分**就是答案。 而如果我们假设$LCP(i,j)=T$，如果字符串$sa(i)$的开头是$T+a$的话，那么在这一连串相邻后缀中，**一定有两个这样的后缀满足一个是$T+x+\cdots$，另一个是$T+y+\cdots$，其中$a<x<y$。**那么此时这两个后缀的$LCP$就是答案了。显然其它位置的答案不会比这个更劣，因为字符串$sa(j)$的开头也是$T$，因此这一连串的字符串开头都是$T$。从上述证明也可以看出这个等式是一个充分条件。 ### $height,h$ 这两个东西都是用来求$LCP$的。 设$height(i)=LCP(i-1,i),h(i)=height(rank(i))$，显然$height(i)=h(sa(i))$。在实际意义上，因为$height(i)$指的是**排名为$i$与$i-1$的后缀的$LCP$**，所以$h(i)$指的是**起始下标为$i$及它的前驱后缀的$LCP$**。 $h\ Theorem:$ $$h(i)\ge h(i-1)-1$$ ~~因为没有名字所以瞎取了一个~~ 这条定理看起来非常神奇，网上也有许多的证明方法。 然而上文我已经给出了$h(i)$的实际意义，再来看看这个定理，你就会发现它非常显然： **假设$LCP(rank(i),rank(i)-1)=S$，这意味着对于起始下标为$i$的后缀，有一个其它的后缀跟它有一个重复的部分是$S$。然后我们考虑$LCP(rank(i-1),rank(i-1)-1)$，显然起始下标为$i-1$的后缀比$i$多了一个字符在前面。我们假设这个字符为$x$，那么，对于$LCP(rank(i-1),rank(i-1)-1)$最优秀的情况就是$=x+S$。这个字符串的长度显然是$\vert S\vert+1$**。所以，这种情况下$h(i)=h(i-1)-1$。那么对于更劣的情况，$h(i)>h(i-1)-1$。综上，在任何情况下$h(i)\ge h(i-1)-1$。$Q.E.D.$ 讲了这么多，可以来写一下$h$怎么求了。其实很简单~~虽然我没想出来~~，我们可以直接枚举$i$，记上一次的答案为$ans$，首先让$ans--$，然后我们找到它的前驱对应的位置，也就是$sa(rank(i)-1)$。 显然当前答案至少是$ans$，那么我们直接从这两个字符串的$ans+1$位开始，直接暴力扫$LCP$长度就可以了。显然因为$ans$最多的变化是$O(n)$的，时间复杂度也是$O(n)$的。 ### $Construction:$ 详情见$Tascho,2.$。**这里不介绍倍增或$DC3$算法**。 $P.S.$尽管该算法时间复杂度为$O(n|S|)$，$S$为字符集，然而其确实很好写。 ### $Application:$ ### $LCP:$ 由于我们求出了$height$，根据$LCP\ Theorem$，两个前缀的$LCP$就是一连串的$height$的$\min$。 那么我们可以进行类似$ST$表的倍增，然后就能$O(1)$回答两个后缀的$LCP$询问了。 ## $47.Partially\ Order/Dilworth\ Theorem$ 偏序关系是一种二元关系。这种关系有三个性质： 自反性：$\forall x\in S,x\le x$； 反对称性：$\forall x,y\in S,x\le y,y\le x\to x=y$； 传递性$\forall x,y,z\in S,x\le y,y\le z\to x\le z$。 链指的是任意两个元素之间可比（譬如$a\le b$,$a$与$b$可比）的偏序集，反链则是任意都不可比。 $Dilworth$定理指的就是，在一个偏序集里的最长反链长度等于最小链覆盖数。 不会证，可以去网上看。 ## $48.Cost\ Flow$ ### $Definition:$ ### 费用 网络流的费用，指的是对于一条边来说，一个单位流量流过需要花费的代价。 最小费用可行流指的是在流可行的前提下所需要的最小费用。 最小费用最大流指的是**在最大流的前提下所需要的最小费用**，不要反过来。 ### $Construction:$ 惊闻原始$-$对偶算法就是$Dinic$费用流，但我看上去并不是，等我先搞清楚两者的关系再写吧。 不过可以肯定的是，$Dinic$费用流也能做到原始$-$对偶的许多优点，只是不清楚能不能处理负权边来用$Dijkstra$代替之后的$SPFA$。 ### $Application:$ ### $Upper\&Lower\ Bound\ CF$ 可以直接类比上下界网络流的写法。注意可行流中，$S,T$连的点的费用都是$0$。 ### 消圈 不清楚这个东西在英语中怎么说。 在费用流解题中，我们经常会遇到有负权回路（**“负权”指的是费用**$<0$）的情况，这种时候因为增广路算法对负权回路的处理不够优秀，我们应该预先处理负权边再进行增广路算法求费用流。 这个过程和上下界的处理有点像，当我们遇到一条负权边的时候，我们让这条边强制满流，然后修改它的盈余量（实际上这个概念在上下界网络流中已经应用过，只是没有定义）。 之后的处理和上下界可行流一模一样，$in>out$附加流$in<out$直接被$SS$连$in-out$，反之亦然。 然后如果有源汇也是$T\to S$连$\{+\infty,0\}$的边，然后在虚拟源汇上跑最大流看是否满流，如果找到了可行流就在残量网络上跑$S\to T$最大流就可以了。 ## $49.Min\_25\ Sieve$ $Min\_25$筛在非中国地区的称呼应该叫“$Extended\ Eratosthenes\ Sieve$”~~我怀疑在日本都不叫$\sout{Min\_25}$筛~~，主要用来解决一类积性函数的求和问题，这类函数满足它质数及质数次幂的值可以很容易地求出来（通常情况下是一个**极简单的**多项式（至少得完全积性，并且能够快速求出$g(n,0)$），我们设它为$f(x)$），也就是求： $$\sum_{i=1}^n F(i)$$ 那么，接下来开始吧。 ### $1.$质数部分之和 我们先求求它： $$\sum_{i=2}^n f(i)$$ **注意此处求的是**$\sum f(i)$**，而不是**$\sum F(i)$。所以请不要觉得把这个求出来了就能求答案，这个求和只是把任意一个数按照质数的这个多项式求的函数值求和而已。 定义 $$g(n,j)=\sum_{i=2}^n[i\in P\ or\ \min(p)>P_j,p\vert i,p\in P]f(i)$$ 翻译成人话就是，$g(n,j)$表示一些数的$f(i)$和，这些数要么是质数，要么满足**最小质因子**$>P_j$。这个东西是这么计算的： $$g(n,j)=\left\{\begin{aligned}&g(n,j-1)&P_j^2>n\\&g(n,j-1)-f(P_j)(g(\frac{n}{P_j},j-1)-g(P_j-1,j-1)/\sum_{i=1}^{j-1}f(P_i))&P_j^2\le n\end{aligned}\right.$$ 我们来解释一下上面这个式子。 首先，对于$P_j^2>n$的情况来说，我们先假设它前面的$P_{j-1}^2\le n$。那么根据$g$的定义，如果不是质数，那它要求$\min(p)>P_{j-1}$，也就是至少是$P_j$。那么以$P_j$作为最小质因子的数如果不是质数，那么至少也是$P_j^2$，它已经不在$n$的范围内了，根本就没有在答案里出现过，因此没有必要再筛任何数了。而当$P_{j-1}^2>n$的时候同理。 **** 然后我们再来考虑$P_j^2\le n$的情况。这种情况意味着对于$g(n,j-1)$来说，你需要筛掉一些最小质因子是$P_j$的数。 我们先看看前面那个$f(P_j)g(\frac{n}{P_j},j-1)$是个啥。 我们的目的是筛出所有最小质因子$=P_j$的数，因此$>P_j$的我们不能要。怎么减掉呢？那我们首先就把一个质因子$P_j$拿出来，因为$f$是完全积性函数，那么这样做就是正确的。 于是剩下的就是$\frac{n}{P_j}$，我们需要在$\le\frac{n}{P_j}$的数中找出最小质因子$\ge P_j$的，这样才能保证正确性。这个东西就是$g(\frac{n}{P_j},j-1)$，$j-1$代表$>P_{j-1}\Leftrightarrow\ge P_j$。 但我们发现我们一不小心把那些$<P_j$的质数也减掉了。这些质数乘上$P_j$会变成一个最小质因子$<P_j$的数，然而这些数在之前已经被筛过了，因此这次我们不能再筛。所以我们要把它们还原，也就是在里面减去一个$g(P_j-1,j-1)$，实际上就是$<P_j$的质数的$\sum f$~~，毕竟要在$\sout{P_j-1}$里找一个最小质因子$\sout{\ge P_j}$的数还是不大现实的~~。 **** 这一部分的时间复杂度被证明为$O(\frac{n^{\frac{3}{4}}}{\log n})$，与洲阁筛的证明似乎是类似的。但好像在$n=10^{13}$时仍然拥有不错的表现。 那么，我们的标题里说了，这是用来求“质数部分之和”。显然求这个和对于合数来说并不适用，我们只要也只能选取质数的和，这个和，也就是$g(n,\vert P\vert)$可以被计入答案。 最后让我们观察一下$g$的本质。可以发现，这就是一个埃筛的过程，即每次用最小质因子筛掉它的倍数。 **** 下面讲讲实现。 首先我们要把$\sqrt n$里的质数筛出来，也要把这里面的质数部分之和预处理出来。可以适当预处理多一点以加快实际效率。 然后，如果是递归版，我们可以直接模拟。下面写到的都是在递归函数中的变量。 当我们的$n\le lim$（$lim$即预处理大小限制）并且$prime[j]^2>n$的时候，我们就可以直接运用我们预处理的答案了。 至于$prime[j]^2>n$，我们可以直接让$j$缩小到$\le$为止。 然后我们令$ans=g(n,0)$，之后枚举每个质因数，直接一路递归下去，每枚举一个就减一下答案。后面那个$g(P_j-1,j-1)$是预处理好的$sum[P_{j-1}]$，可以直接减。 如果是递推版，我们就可以看看这个函数的计算到底干了啥。 我们注意到$\lfloor\frac{n}{i}\rfloor$最多只有$O(\sqrt n)$种取值~~（显然分类讨论可得出）~~，那么我们首先计算出$O(\sqrt n)$个初值，也就是$g(x,0)$，然后就可以从小到大枚举最小质因子（也就是$j$），然后**从大到小**枚举这个整除的取值（从小到大递推会重复~~，参考$\sout{01}$背包与完全背包~~），就可以直接递推处理了。能够递推当且仅当$prime[i]^2\le num[j]$，否则直接保留原来答案。 具体可以弄两个数组分别维护当前下标实际代表的数，一个维护$\le\sqrt n$，另一个维护$>\sqrt n$，可以参考[FKB的博客](https://www.cnblogs.com/zjp-shadow/p/9190865.html)。 有一些细节，譬如**初始下标为**$2$、$prime[j+1]^2>n$**而不是**$\ge n$。没注意到这些很容易瞎调很久调不出。 还有就是注意你$Min\_25$中的$n$和实际的$n$是不一样的$\cdots\cdots$注意区分好。 ### $2.$合数部分之和/总和 有了$g$，接下来我们可以求合数部分/总体的答案了。 定义 $$S(n,j)=\sum_{i=2}^n[min(p)\ge P_j]F(i)$$ 翻译成人话就是，$S(n,j)$表示一些数的$F(i)$和，这些数满足**最小质因子**$\ge P_j$。 下面我们终于可以使用积性函数的性质了。 $$S(n,j)=g(n,\vert P\vert)-g(P_j-1,j-1)/\sum_{i=1}^{j-1}f(P_i)+\sum_{i=j}^{P_i^2\le n}\sum_{k=1}^{P_i^{k+1}\le n}(F(P_i^k)S(\frac{n}{P_i^k},i+1)+F(P_i^{k+1}))$$ 这个式子比较容易理解，首先前面部分是在求质数的贡献，但是我们必须要除掉最小质因子$< P_j$的情况；后面部分就是在利用积性函数的性质，把合数拆成质数的乘积就可以了。我们枚举组成这个合数的最小质因子是什么，它的次幂是多少（注意是$P_i^{k+1}\le n$因为我们从$1$开始枚举），然后就可以往下递归，或者也可以只用这一个质因子构成这个合数，那么$k$应该$\ge 2$，所以之后的答案要加上$F(P_i^{k+1})$。 求完了这个式子，答案就是$S(n,1)+f(1)$。 这一部分的实际时间复杂度被证明是$O(n^{1-\omega})/O(\frac{n}{\log n})$的，但这个上界非常松，以至于它也能在$n=10^{11}$时取得不错的表现，似乎可以被证明在这个范围内运算次数是$O(\frac{n^\frac{3}{4}}{\log n})$的。 **** 下面讲讲实现。 求$S$对递推显然不太友好，因为第二维并不是可以直接确定的。因此只能使用递归处理，不过也够用。而为了求$S$的方便，求$g$采用递推式。 首先$n\le 1/P_i> n$直接$\rm return\ 0$。 有一个细节是**是$i+1$而不是$k+1$，不要手残写错。** 好像就没有什么值得注意的细节了。似乎就是直接模拟。 ## $50.Disjunction-Conjunction\ Tree$ 求析合树官方英文$\cdots\cdots$ 析合树是一种能够用来表示一个序列所有连续段的集合的一种树。 ### 前置定义 **连续段/不动点：**一个区间$[l,r]$满足其中的所有数排序后的差分序列所有数均为$1$。 **基：**与线性代数中的定义相同，表示一个连续段集合$S$满足$S$内所有元素可以通过交/并生成所有连续段。我们需要求得的是极小基，即一个当且仅当满足它的子集不存在基的基。 **本原连续段：**~~似乎字符串里有本原串的定义，不知道是啥。~~一个满足不存在与它相交并互不包含的连续段的连续段。我们设本原连续段集合为$M$。 **本原连续段生成树：**若存在一棵有根有序树$T=(V,E)$存在一个双射$f:V\leftrightarrow M$，使得满足$\forall u\in V,f(u)=\cup f(son_u)$，其中$[a,b]\cup[b+1,c]=[a,c]$，其余情况无意义，称其为**连接**（$son_u$指的是$u$儿子的**有序**集合）；那么我们称这棵树为置换$p$的本原连续段生成树，也就是析合树。 人话就是说所有儿子互不相交，然后排序之后接起来就是当前结点表示的连续段。 **平凡段：** ### $Properties:$ 析合树的性质非常丰富。 ### 析合树上结点的性质（引理） $1:son[u]$所有非平凡段的连接都是连续段； $2:son[u]$所有非平凡段的连接都不是连续段。 证明： ### 合点 合点指的是满足$C_1(son[u])$的结点。 首先，叶子节点显然全为合点。此外，除叶子结点外，每个合点最少有两个儿子。 ### 析点 析点指的是满足$C_2(son[u])$的结点。 每个析点最少有四个儿子。 ### $Construction:$ 析合树的构造是一个$O(n)$的离线算法。~~这也就意味着它可能会被应用到某些毒瘤卡$\sout{O(n\log n)}$的题中。~~ ### $Application:$ 很遗憾，由于~~毒瘤~~$LCA$在$WC$中并没有阐述，因此~~我暂时不知道~~析合树暂时不支持在可接受的复杂度内进行修改操作。希望能有$dalao$教我$qwq$