Mato is No.1

依照CLJ神犇的指示，最近本沙茶決定開(kāi)始被數(shù)據(jù)結(jié)構(gòu)題虐……先找來(lái)了省內(nèi)的一道題（就是這道囧）……

題目大意：求兩個(gè)長(zhǎng)度為5N的序列的最長(zhǎng)公共子序列長(zhǎng)度，在兩個(gè)序列中，整數(shù)1~N分別都出現(xiàn)5次。1<=N<=20000。

【注：本沙茶一開(kāi)始用線段樹(shù)的，后來(lái)在看了CLJ神犇的標(biāo)程（Orz！！）之后終于明白了樹(shù)狀數(shù)組解法囧……】

LCS問(wèn)題的樸素時(shí)間復(fù)雜度為O(NM)。對(duì)于本題顯然需要優(yōu)化。
觀察LCS的轉(zhuǎn)移方程：
F[i][j] = F[i-1][j-1]+1（當(dāng)A[i]==B[j]時(shí)）
F[i][j] = max{F[i-1][j], F[i][j-1]}（當(dāng)A[i]!=B[j]時(shí)）

可以將F用滾動(dòng)數(shù)組來(lái)表示，即設(shè)F'為上階段的F（即F[i-1]），則本階段的F（即F[i]）可以由F'求得：
F[j] = F'[j-1]+1（當(dāng)A[i]==B[j]時(shí)）
F[j] = max{F'[j], F[j-1]}（當(dāng)A[i]!=B[j]時(shí)）

進(jìn)一步，這個(gè)F'其實(shí)都不用記錄，只需在每一階段更新一遍F即可：
F[j] = F[j-1]+1（當(dāng)A[i]==B[j]時(shí)）
F[j] = max{F[j], F[j-1]}（當(dāng)A[i]!=B[j]時(shí)）
不過(guò)需要逆序更新（保證F[j-1]是上一階段的而不是本階段的），這與01背包有點(diǎn)像。

由題意可以發(fā)現(xiàn)，A[i]==B[j]的出現(xiàn)次數(shù)極少，在每階段中只會(huì)出現(xiàn)5次！我們可以預(yù)先求出這5個(gè)地方的值，然后對(duì)于其它的F[j]，其在本階段的值其實(shí)就是它前面的最大值（max{F[1..j-1]}），又因?yàn)槲覀冏詈笾恍柚繤[N']（N'=5N，即序列長(zhǎng)度）即可，故可設(shè)計(jì)出以下算法：
一開(kāi)始F[1..N]均為0，然后將以下內(nèi)容執(zhí)行N'次，第i次：
（1）求出B序列中與A[i]相等的5個(gè)元素的位置，設(shè)為S[1..5]；
（2）依次更新F[S[5..1]]，每個(gè)都更新為它前面的最大值加1（很容易知道為神馬），其它的值暫時(shí)不管；

N'次執(zhí)行完后，整個(gè)序列中的最大值就是F[N']的值。由于這個(gè)算法中出現(xiàn)的主要操作是改動(dòng)一個(gè)指定位置元素的值和找一個(gè)前綴區(qū)間中的最大值，因此可以采用樹(shù)狀數(shù)組，時(shí)間復(fù)雜度O(NlogN）（線段樹(shù)必TLE）。

【總結(jié)：在本題中使用了一種“推遲更新”的方法，即需要更新一個(gè)值時(shí)，先暫時(shí)不理它，等到需要引用到它的時(shí)候再更新。這種方法最常見(jiàn)的應(yīng)用就是線段樹(shù)的結(jié)點(diǎn)標(biāo)記。不過(guò)要注意的是，如果該值的推遲更新會(huì)對(duì)它后面要更新的值帶來(lái)問(wèn)題（也就是，這些后更新的值需要引用該值的新值），就不能使用這種方法。在本題中，其它位置的值的改變只與這5個(gè)特殊的位置有關(guān)，與其它因素?zé)o關(guān)，故可以使用這種方法。】