关于各种神奇的倍增法 倍增 其实倍增法不仅局限于快速幂，后缀数组，STSTST表，求lcalcalca之类的特定算法，而是用来解决一类特定问题的。 倍增原理 看似玄学的倍增其实源于两个数学等式 1. 2. {中pi为N的二进制第i位} 想必任何一个知道二进制的人都明白上述两个等式吧…… 而倍增法的唯一要求的是，被称之为“+”的运算满足结合律(有些人也成操作满足可合并性) 具体来讲，倍增法用到的地方一般是，我们现在要询问/修改一些东西，然后我们发现操作具有合并性，之后呢，我们对于每个大小为2i2^i2i的东西预处理出来一个答案，等到询问的时候，就将询问的东西大小用二进制表达，将预处理出来的每个东西合并起来就得到了答案 常用的两类二进制拆分代码 其中上面一个适用于ppp已知的情况(比如倍增求lca，跳到深度相等的那段代码) 下面的一个适用于ppp未知，但是可以比较ppp和某个值的大小，以及可以做相减运算 (比如lcalcalca第二段，两个点一起向上跳，但是不知道lca的深度的情况，但是我们用这个代码在未知lcalcalca深度的情况下对lcalcalca深度做了二进制拆分) 然后我们来结合这道题讲一下如何魔改倍增法，因为这个玩意和dpdpdp，分治法都很像，都是根据某一个问题的性质设计了类似的"方法"，根本不是有板子的算法，所以我们要具体问题具体分析…… 本题题解 首先我们发现题目中给了我们一些区间相等的关系，之后我们发现，如果从子串的思路想会进入死胡同，因为串都没给你哪里来的后缀数据结构？ 发现这道题本质上是个计数问题，我们考虑枚举每个点可以取的值，发现有些其他点必须和他取值一样，否则不满足题意区间相等的要求，(这里其实做了一步转化，区间相等<-->对应点相等) 那么我们就有办法维护这个相等关系了,直接并查集维护复杂度O(n2)O(n^2)O(n2)，30ptsget√30pts get√30ptsget√，最后的答案为9∗10(num−1)9*10^(num-1)9∗10(num−1) num为并查集个数，因为最高位是不可以取零的 然后发现是传统暴力的复杂度不均衡问题，我们的处理询问，是O(N2)O(N^2)O(N2)的但是，我们的查找，仅仅是O(N)O(N)O(N)的……所以我们要平衡这个扭曲的复杂度，使得询问查找都变成O(NlogN)O(NlogN)O(NlogN) 那么怎么办呢，并查集的并操作具有可合并性，所以我们可以考虑上倍增。 我们可以将一个点拆成logNlogNlogN个点，分别代表从点i开始，长度为2k2^k2k的子串 那么当我们处理两个区间相等的关系时，对区间做二进制拆分，拆成logloglog个区间，分别并起来即可 当然我们这样做修改是省心了，但是同时查询的时候也会带来一些麻烦……因为，我们要求的信息是最底层的，只能是长度为1的区间，而不能有奇奇怪怪的区间 不过没关系，我们这时运用等式1，拆分并查集 具体来讲，我们从最长的区间开始逐个枚举，每次查找他和他的父亲，然后把它和父亲都劈成两半，前一半和前一半连边，后一半和后一半连边即可，这样相当于把较长区间并查集拆成两个一半的并查集 最后我们就有了一些关于那些点相等的信息，直接计算并查集个数即可