某島

… : "…アッカリ~ン . .. . " .. .
July 12, 2021

UOJ #608. 【UR #20】機器蚤分組

題意

https://uoj.ac/problem/608
給定一個字元串 T,每次詢問一個子串 T[l,r],返回其最長重複子串的長度。

做法

證明?參考 官方題解
我們來討論怎麼用 SAM 搞子串的重複子串。

首先回憶怎麼用 SAM 求最長重複子串。
直接返回 fail 樹上非葉子節點的 len[u] 就好。

再考慮怎麼求某個前綴 T[1,r] 的最長重複子串。
我們考慮離線,按照 r 端點從小到大排序,
按照順序每次在 fail 樹上找到前綴所對應的葉子節點,
往根節點染色即可。用染色路徑上第一個碰到的節點的 len 的長度更新答案。
因為每個節點只會被染色一次,所以暴力染色即可。

最後考慮一般情況 T[l,r],我們顯然需要對染色進行區分,
我們希望每個狀態越晚被染色越好,因為越晚,它可能對答案的貢獻就越長。
我們不妨畫一下示意圖。。考慮下面的情況。。考慮到時刻 r 的時候經過節點 u。
u 歷史上在時點 l1 和 l2 都被染色過,且 len[u] = 4,那麼有:
設 l1 < l2 < r。
—l1, —l2, —r
那麼我們可以忽略 l1,並且只有在 l <= l2-3 的時候,才能得到
完整的 4 長度的貢獻,在 l2 時刻,因為詢問的左區間不夠長,只有對答案帶來 1 的貢獻。

具體說來,不妨對每個可能三元組 (l,r,u)。
r 表示當前染色的時點,l 表示歷史上這個節點最晚被染色的時點。
u 表示 l, r 到根路徑上的某個公共祖先。

我們可以用線段樹。。。
支持詢問區間最值,
以及區間覆蓋,和區間等差數列覆蓋兩個操作即可。

具體說來就是。。。
checkMax1(1, l-len[u], len[u]),表示對區間 [1, 1-len[u]] 與 len[u] 取 max。
以及
checkMax2(l-len[u]+1, l),表示對 l-len[u]+1, l-len[u]+2,…, l 這個區間分別 checkMax 上 l, l-1, …, 1 這個遞減數列。

因為染色過程總是葉子到根節點的路徑,所以可以用動態樹。
這裡的動態樹也可以用啟發式合併替代。