Mato is No.1

依照CLJ神犇的指示，最近本沙茶決定開始被數據結構題虐……先找來了省內的一道題（就是這道囧）……

題目大意：求兩個長度為5N的序列的最長公共子序列長度，在兩個序列中，整數1~N分別都出現5次。1<=N<=20000。

【注：本沙茶一開始用線段樹的，后來在看了CLJ神犇的標程（Orz！！）之后終于明白了樹狀數組解法囧……】

LCS問題的樸素時間復雜度為O(NM)。對于本題顯然需要優化。
觀察LCS的轉移方程：
F[i][j] = F[i-1][j-1]+1（當A[i]==B[j]時）
F[i][j] = max{F[i-1][j], F[i][j-1]}（當A[i]!=B[j]時）

可以將F用滾動數組來表示，即設F'為上階段的F（即F[i-1]），則本階段的F（即F[i]）可以由F'求得：
F[j] = F'[j-1]+1（當A[i]==B[j]時）
F[j] = max{F'[j], F[j-1]}（當A[i]!=B[j]時）

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

由題意可以發現，A[i]==B[j]的出現次數極少，在每階段中只會出現5次！我們可以預先求出這5個地方的值，然后對于其它的F[j]，其在本階段的值其實就是它前面的最大值（max{F[1..j-1]}），又因為我們最后只需知道F[N']（N'=5N，即序列長度）即可，故可設計出以下算法：
一開始F[1..N]均為0，然后將以下內容執行N'次，第i次：
（1）求出B序列中與A[i]相等的5個元素的位置，設為S[1..5]；
（2）依次更新F[S[5..1]]，每個都更新為它前面的最大值加1（很容易知道為神馬），其它的值暫時不管；

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

【總結：在本題中使用了一種“推遲更新”的方法，即需要更新一個值時，先暫時不理它，等到需要引用到它的時候再更新。這種方法最常見的應用就是線段樹的結點標記。不過要注意的是，如果該值的推遲更新會對它后面要更新的值帶來問題（也就是，這些后更新的值需要引用該值的新值），就不能使用這種方法。在本題中，其它位置的值的改變只與這5個特殊的位置有關，與其它因素無關，故可以使用這種方法?！?br>