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部分）：
下面是優化的實測結果（第一個為優化后的，第二個為優化前的），可以看出，該優化的力度很大。