Mato is No.1

     摘要: 【例题】[SDOI2011]染色（注：数据范围木有交代，应为：点数N<=105，操作数M<=105，所有的颜色C为整数且在[0, 109]之间。一、树的路径剖分当中点权型（点上有权值而边上木有）的处理办法：（1）找重链建线段树的时候，w0中存储tot+1个数，为该重链自上而下的各点的权值（例题中为颜色）；（2）除了父边是轻边的叶结点之外，树中的每个结点都属于且仅属于一条重链（根据定义得...  阅读全文

     摘要: 原题地址【有关树的路径剖分的东东在网上介绍的太多了……】常见的路径剖分的方法是轻重边剖分，即把树中的边分为轻重两部分，方法：设SZ[i]为以i为根的子树的大小（结点总数），则若点x不是叶结点，则其子结点中SZ值最大的（注意，有多个SZ值最大的子结点应任选一个，只能选一个，防止出现重链相交，引发歧义）点y，边(x, y)称为重边，其余的边都是轻边。首尾相连的重边称为重链（注意...  阅读全文

【本沙茶以前曾经搞过矩形的面积并、周长并问题，当时几乎是抄神犇代码的，根本木有理解，现在在看了扫描线以后理解一些了】
“扫描线”严格来说不是算法，而是一种思想，它在解决很多几何问题或者矩阵问题中有大用。所谓“扫描线”，就是用一条假想的直线（一般是水平或者竖直的）沿x轴（或y轴）方向扫过整个平面，在此过程中，每当发现有特殊事件（比如插入、删除事件等），就执行这一事件。一般来说，它需要配合数据结构进行加速，常用的数据结构有线段树、平衡树、树状数组、堆、凸多边形集合等。

【1】矩形的面积并和周长并问题：
这个在以前总结的那一篇里面曾经说明过，这里只是补充一下。

对于面积并，可以假想一条水平直线沿y轴正方向扫过整个平面，每当遇到矩形的上下边界，就插入或删除一条线段（上边界为插入，下边界为删除），在每两个相邻上下边界之间得到覆盖面积为：目前插入（尚未删除）的所有线段覆盖的总长度乘以两边界间的距离。显然，求前者需要用离散化（横坐标）+线段树实现。

这里讲一下离散化的步骤和易疵点：首先将要离散化的数据（设为A数组）存储在一个数组B里，然后对B排序（一般是递增排序）、去重（方法：若B长度为0则不需去重，否则B[0]保留，从B[1]开始，若B[i]>B[i-1]则保留B[i]否则跳过B[i]），得到一个新的数组B0，最后，再对原来的A数组中的每个元素在B0中二分查找，找到其位置即可。显然，对N个数据离散化时间复杂度为O(NlogN)，具体实现时，可不设B0，直接存在B里面（见代码）。易疵的地方主要是B的长度为0的情况。 其中n0为数据个数，n为去重后的数据个数（也就是离散化后的编号范围，很重要的！），find_x为二分查找过程。

对于周长并可以这样理解：照样是水平直线沿y轴正方向扫过整个平面，照样是遇到矩形的上下边界就插入或删除，这样，周长的水平部分是很好得到的，只要统计每两个相邻上下边界的线段覆盖总长之差即可，对于竖直部分则需要统计被线段覆盖的端点个数——或者说，需要统计至少作为一条目前插入线段的端点，且木有被任何一条线段内部包含的端点个数（因为只有这些点所延伸下来的竖直线段有可能作为周长的竖直部分）。维护方法：给每个结点设立ss、lbd与rbd，分别表示该结点区间内这种点的个数，以及该线段区间的左右端点是不是这种点。lbd=LCH.lbd; rbd=RCH.rbd; ss=LCH.ss+RCH.ss-2*(LCH.rbd || RCH.lbd)（因为我们需要的是线段树而不是点树，因此其中的每个叶结点表示的实际上是一条单位线段，而不是一个点，这样，LCH区间的右端点与RCH区间的左端点其实是同一个点，如果它们都是这种点，则都不能算，因为被包含在内部了）。例外的是，如果某个结点区间完全被某条插入线段包含，则ss为2，lbd、rbd均为1（这个结果可能不正确，因为可能左右端点被包含在内部，因此，整棵树上只有根结点的ss值是绝对正确的ss值，其余结点都需要特判）。这样，根结点的ss值就是这种点的个数，乘以两相邻上下边界的距离就是之间的竖直部分总长度。

代码：
面积并（HDU1542）
周长并（HDU1828）

（此外，周长并还有一种更容易理解的算法：就是先求出水平部分总长后，将所有的矩形旋转90度，再求一次水平部分总长，这就是原来的竖直部分总长了）

【2】应用：
PKU2482

有一类动态规划（其中也包含递推）问题，要求满足一些限制条件的字符串，这些限制条件是“需要含有某个子串”或“不能含有某个子串”，那么KMP、AC自动机等就有大用了。

【例1】HDU3689
题意：字符集中有一些字符，给出每个字符的出现概率（它们的和保证为1），再给出一个子串B，求：任给一个长度为N的字符串A（只能包含字符集中的字符），使得S是A的子串的概率。

求解这类问题首先要进行补集转化。因为子串可能有重叠（比如"ababa"中就出现了两个"aba"），所以先转化为“求任给一个长度为N的字符串A（只能包含字符集中的字符），使得B不是A的子串的概率”，然后再用1减去这个概率即为结果。
设F[i][j]为“在所有长度为i的不出现B的字符串中，后缀与B的前缀匹配长度为j（即该字符串的后缀与B的前缀的最大匹配长度为j）的概率”，很显然，F是由递推得到了，关键是如何进行状态转移？或者说，在递推过程中，哪些状态可能成为F[i][j]的前趋状态？
假设F[i-1][k]是F[i][j]的前趋状态，也就是说，在字符集中至少存在一个字符c，使得主串的第i位（最后一位）取c时，能够从F[i-1][k]转移到F[i][j]。这就需要求一个值S[k][c]，表示当主串的后缀与B的前缀的（最大）匹配长度为k时，在主串后再加上一个字符c，其匹配长度会变成什么。举例：设目前主串A'="abasab"，B="asabs"，其匹配长度为4，若在A'后加上一个字符's'，则匹配长度变为5，所以S[4]['s']=5，而若在A'后加上一个字符'a'，则匹配长度会变成1，所以S[4]['a']=1。显然S值和A前面的哪些字符是没有关系的。
那么这个S值如何计算？其实可以发现，S和KMP算法中的nx数组神似，因此完全可以按照计算nx数组的办法来计算S。具体来说，先要对B作KMP自身匹配，求出其nx数组，然后，在求S[k][c]的时候，尝试在B的第k位（由于B的下标从0开始所以B[k-1]）后加上字符c，看看会“回退”到哪里即可。代码： 这里m是B的长度。注意，当i=m时，S[i][j]是无意义的，因为前面已经说过了不能出现B。
在求出S值后就能求出F值了。对于状态F[i][j]，若存在一个字符c使得x=S[i][c]（满足0<=x<m），则F[i][j]是F[i+1][x]的前趋状态。当然，由于本题是求概率而不是求总数，且每个字符出现的概率还不一样，所以转移的时候，应是将F[i+1][x]加上F[i][j]*P[c]（P[c]是字符c出现的概率），边界：F[0][0]=1，F[0][1..m-1]均为0。
最终结果为1-∑F[N][0..m-1]。

代码

【例2】PKU1625（URAL1158）
题意：给出一些子串，求长度为N，各个字符都属于给定的字符集的所有字符串中，不包含任何一个给出的子串的字符串个数（需要使用压9位的高精度）。

本题显然是【例1】的多子串形式，而用来解决多个字符串同时匹配的只有AC自动机，那么如何在本题中使用AC自动机求解呢？
观察【例1】中的F[i][j]，可以想象一下，一个图中有m个顶点，分别表示匹配长度为0..(m-1)，然后不断新加入的字符让这些状态在这些结点间不断转移（状态转移就是图中的边），这样，F[i][j]就表示“阶段i到达结点j上”。而AC自动机是基于Trie（树）的，其中有现成的结点，这就揭示了本题的状态：
F[i][j]表示长度为i的合法的字符串（就是满足字符集限制且不包含任何一个给定子串）中，在匹配到最后一位（第i位）后，刚好到达结点j的字符串的个数。
同样，S[k][c]表示“目前到达结点k，接下来的一个字符是c的时候，会到达哪个结点。在对所有的子串建立了自动机之后，S值只要类似地搞就能求出来了。然后F的转移也就搞定了。
不过，本题要万分注意AC自动机的一个BUG：在建立了自动机以后，需要把所有本身不危险（如果一个结点代表的字符串刚好是某一个给出的不能出现的子串，则该结点是危险结点），但通过失败指针不断上溯能够到达一个危险结点的结点，也标记为危险结点，比如两个子串是"abcde"和"bc"，则代表"abcd"的那个结点由于包含了"bc"所以也是危险的。
此外，本题的输入要注意，字符集的ASCII码范围是-128~127，所以必须用char而不是unsigned char，且由于可能包含空格所以必须用gets()而不是scanf()输入，又因为C/C++中木有负数下标，因此在输入之后还要转化一下（加128）。

代码

【例3】PKU3691
题意：给出一些子串和一个字符串A（其每个字符均属于字符集{'A', 'C', 'G', 'T'}），求至少要改动A的几个字符（不能改成不属于字符集的字符），使得它不包含任何一个给出的子串，若不管怎么改都不行，则结果为-1。

这就是真正的DP了。设F[i][j]为前i位，到达的结点为j，最少改动的字符个数，则转移方程为
F[i][j] = min{F[i-1][x] + (A[i] != c)}，c∈{'A', 'C', 'G', 'T'}，S[x][c]=j。边界：F[0][root]=0，其余的F[0][]=+∞，A的实际下标从1开始。
求S数组的方法见【例2】

代码

【例4】PKU3208
题意：含有连续的三个数字6的正整数，称为"beastly number"，求第P个（1<=P<=50000000）"beastly number"（其位数不会超过15位）。
（这题是本沙茶在PKU上至今为止，自己想出算法的AC人数最少的题）
本题其实是用不着KMP的，因为"666"这样简单的子串……

思路：由于位数不会超过15位（后来发现最多只有10位），所以每个"beastly number"都可以看成一个长度为15，字符集为['0'..'9']的字符串（注意是可以有前导0的，因为位数可能不足15位）A，整个过程也就是从高位（第0位）向低位（第14位）求出A的各位。

预处理：求出F[i][j]，表示若A的前i位已经确定（其中不含"666"，准确来说是非末尾不含"666"），且前i位的末尾刚好有j个'6'（j的范围是0到3）时，有多少个"beastly number"（注意，前i位既然已经确定，就不可更改了，能够决定的只有第i位的后面）。
显然先要求出F0[i][j]表示有多少个不是"beastly number"。其递推方程不好写，见代码（其实也是很好理解的）。然后F[i][j]=10^14-i - F0[i][j]。

然后就是不断调整边界来构造了。准确来说，设前i-1位已经确定，现在要确定第i位，则枚举第i位是0~9中的哪个值，然后求出满足条件的最小的"beastly number"和最大的"beastly number"的名次（注意，名次是从1开始的），看看P在不在其中，这样就能确定了。严重注意：如果已确定的位数中已经出现了"666"，接下来的就不用枚举了，直接在后面接上P-L就行了，L为左边界。

但是，为什么要把本题放在KMP的专题里面呢囧？因为如果这个子串不是"666"而是一些结构复杂的东东比如"123131"这样的，只有借助KMP算法了。这时，F[i][j]就表示 A的前i位已经确定（非末尾不含这个子串），且其后缀与这个子串的前缀匹配长度为j，有多少个"beastly number" ，转移方程与前几个例子类似。

代码

总结：
KMP算法和AC自动机的状态转移性质决定了它们在字符串匹配类DP问题中的巨大作用。在实际应用中，要注意灵活使用它们。此外，AC自动机的那个BUG是一定要注意的。

【后缀数组真难懂啊啊……就20+行的代码搞了几天才理解……不知是不是我太沙茶了】

【1】一些定义：
字符串：广义的字符串是指“元素类型有序，且元素值有一定范围的序列”，其元素不一定非要是字符，可以是数字等，因此整数、二进制数等也是字符串；
字符集：字符串的元素值的范围称为字符集，其大小记为SZ。
字符串的长度：字符串中元素的个数，一般记为N，长度为N的字符串A第一次提到时一般用A[0..N-1]来表示；
前缀：字符串A[0..N-1]的从A[0]开始的若干个连续的字符组成的字符串称为A的前缀，以下“前缀i”或者“编号为i的前缀”指的都是A[0..i]；
后缀：字符串A[0..N-1]的到A[N-1]终止的若干个连续的字符组成的字符串称为A的后缀，以下“后缀i”或者“编号为i的后缀”指的都是A[i..N-1];

对于一个长度为N的字符串，将其N个后缀按字典序大小进行排序，得到两个数组sa[i]和rank[i]，sa[i]为排在第i位的后缀的编号（也就是一般说的ord[i]），rank[i]为排在后缀i排在的位置（称为后缀i的名次）。sa、rank值的范围均为[0..N-1]。sa和rank互逆，即sa[i]=j等价于rank[j]=i，或者说成sa[rank[i]]=rank[sa[i]]=i。这里，sa称为后缀数组，rank称为名次数组。

【2】用倍增算法求后缀数组：
在论文里，后缀数组有两种求法：倍增算法和DC3算法，前者的时间复杂度为O(NlogN)，但常数较小，后者的时间复杂度为O(N)，但常数较大，在实际应用中，两者的总时间相差不大，且后者比前者难理解得多（本沙茶理解前者都用了几天时间……后者就木敢看了）。这里就总结一下倍增算法吧囧……
首先，贴一下本沙茶的用倍增算法求后缀数组的模板： 这里A是待求sa和rank的字符串。

<1>倍增算法的思想：
记R[i][j]为A[i..i+2^j-1]（如果越界，则后面用@填充）在A的所有长度为2^j的子串（越界则后面用@填充）中的名次（rank）值。倍增算法就是按阶段求出所有R[i][j]的值，直到2^j>N为止。首先，R[i][0]的就是字符A[i]在A[0..N-1]中的名次，是可以直接用计数排序来实现的。然后，若R[0..N-1][j-1]已知，则可以按照以下方法求出R[0..N-1][j]的值：对每个i（0<=i<N），构造一个二元组<X_i, Y_i>，其中X_i=R[i][j-1]，Y_i=R[i+2^j][j-1]（若i+2^j>=N，则Y_i=-∞），然后对这N个二元组按照第一关键字为X，第二关键字为Y（若两者都相等则判定为相等）进行排序（可以用基数排序来实现），排序后，<X_i, Y_i>的名次就是的R[i][j]的值。

<2>一开始，对A中的各个字符进行计数排序： 这个木有神马好说的，在搞懂了基数排序之后可以秒掉。唯一不同的是这里加了一句：rank[i]=A[i]，这里的rank[i]是初始的i的名次，MS不符合rank[i]的定义和sa与rank间的互逆性。这里就要解释一下了囧。因为在求sa的过程中，rank值可能不符合定义，因为长度为2^j的子串可能会有相等的，此时它们的rank值也要相等，而sa值由于有下标的限制所以不可能有相等的。因此，在过程中，rank其实是用来代替A的子串的，这样rank值只需要表示一个“相对顺序”就行了，也就是：rank[i0]>(=, <)rank[i1]，当且仅当A[i0..i0+2^j-1]>(=, <)A[i1..i1+2^j-1]。这样，可以直接将A[i]值作为初始的rank[i]值。

<3>j（代替2^j）的值从1开始不断倍增，对二元组进行基数排序求出新阶段的sa值：
注意这个基数排序的过程是很特别的。首先，它并不是对A在进行排序，而是对上一阶段求出的rank在进行排序。因为前面已经说过，在求sa的过程中，rank就是用来代替A的对应长度的子串的，由于不能直接对子串进行排序（那样的话时间开销很恐怖的），所以只能对rank进行排序。另外，这里在对二元组<x, y>的第二关键字（y）进行排序的过程中加了优化：这些y其实就是把上一阶段的sa整体左移了j，右边空出的部分全部用@（空串）填充得到的，由于空串的字典序肯定最小，因此将右边的空串按照下标顺序先写入临时sa（代码中用tmp表示的就是临时sa，也就是对第二关键字y排序后的ord结果），然后，上一阶段的sa如果左移后还木有消失的（也就是sa值大于等于j的），再按顺序写入临时sa，就得到了排序结果。剩下的对x的排序结果就是上一阶段的sa，唯一不同的是对于x相同的，按照临时名次递增的顺序。

<4>求出新阶段的rank值： 由于下一阶段需要使用本阶段的rank值，因此在求出了本阶段的sa值以后，需要求rank值。（代码中的tmp起了临时rank的作用，目的是节省空间）
因为sa值已经求出，因此只要依次扫描sa就可以得到rank值，唯一要做的工作就是找到哪些子串是相等的，它们的rank值应该相等，除此之外，rank值只要依次加1即可。判定相等的方法：只需判定rank[i]和rank[i+j]是否都对应相等即可。若rank[i+j]越界，用-∞（当然任何一个负数都行，代码中用了-1）来表示。
最后还有一个优化：由于本阶段的名次的范围只有[0..p]这么多，下一阶段的“字符集”（其实就是rank集）的大小SZ可以设为p+1，这样可以省一些时间。

这样后缀数组sa和名次数组rank就全部求完了。

以后还有一些更重要的东东就是AC自动机、后缀数组等的应用问题，算了，以后再搞吧囧。

具体题目见HDU2222，其实就是一个裸的多串匹配的问题（给出一个主串和N个子串，求出几个子串在主串中出现过）。

我真是太沙茶了……这么水的题目调了N久，找了N位神犇帮我看代码，最终才找出来BUG……

易疵点：
（1）本题的子串是可以相同的，此时Trie的每个结点要设一个mul值，表示该结点对应的字符串在所有子串中重复的次数，另外，不要为了省空间把mul定义成char型，有可能所有的字符串全相同，因此需要定义成int（事实证明不会爆空间），这是本沙茶被折磨了这么久的主要原因；
（2）Trie采用静态存储，0号结点作为空结点（NULL），因此真正的结点编号从1开始，另外root一般都是1号结点；
（3）注意在建立自动机以及匹配的时候，所有要沿fail上溯的地方，其边界都是0（NULL，注意不是root）或者找到一个有对应子结点的结点。注意到0还没有找到的处理方法：在建立自动机的时候，将T[j]置为root；在匹配的时候，将x置为root；

代码（模板）（那些标了Attention的地方都是易疵的）：
【2011年10月19日】今天发现了匹配过程中的一个可优化的地方：对于一个点x以及它的所有返回结点（这里把所有沿着x的失败指针不断上溯直到root路径上的结点都称为返回结点），由于不可重复计数，可以将它们的mul值置为原来mul值的相反数（-mul），而不是0，表示该结点已经统计过。这样在下一次y的上溯过程中一旦发现一个mul值为负的点就不用继续上溯了，因为上面的点一定也已经统计过了。
当然，这仅限于单主串，如果是多主串则需要在每次匹配之前把Trie树中所有结点的mul值（如果是负数的的话）全部重新取反。为了节省时间，可以在匹配过程中把所有统计过的（mul值改为负数的）结点全部放进一个辅助的队列里，然后取反时只要处理队列中的结点就行了。

加入该优化后的代码（solve部分）：
下面是优化的实测结果（第一个为优化后的，第二个为优化前的），可以看出，该优化的力度很大。