BZOJ 2119 股市預測：後綴數組 + LCP + RMQ 求 ABA 型子串

題目大意

給定長度 n 的數列，求差分後有多少子串滿足 ABA 形式，其中 B 長度固定為 m，A 長度 > 0 且兩側 A 相同。

核心思路：枚舉 A 長度 + 後綴數組 LCP

1. 對原數列差分，得到新數列 a[1..n-1]。
2. 構造 a + [INF] + reverse(a) 並構建後綴數組 SA、Height 數組、RMQ（稀疏表）。
3. 枚舉 A 長度 j (1..n)。對每個起始位置 i，考慮位置 i 和 i+j+m 的後綴。
   利用 RMQ 查詢兩後綴的 LCP（最長公共前綴）L1（向右擴展）和反轉數列中的 LCP L2（向左擴展）。
4. 合法擴展長度受限於 j：L1 = min(L1, j), L2 = min(L2, j-1)。
   若 L1 + L2 >= j，則貢獻 L1 + L2 - j + 1 個合法子串。

關鍵技術點

• 後綴數組倍增構建 O(n log n)。
• Kasiski 算法求 Height O(n)。
• 稀疏表 RMQ O(1) 區間最小值。
• 差分轉化「相同子串」為「相同差分子串」，巧妙處理數值大小關系。

代碼框架（關鍵部分）

// 後綴數組構建、Height、RMQ 同標準模板
// 主循環
for (int j = 1; j + j + m <= n; ++j) {
    int last = 0;
    for (int i = 1; i + j + m <= n; i += j) {
        int r = min(LCP(rank[i], rank[i+j+m]), j); // 向右
        if (last + r >= j) ans += last + r - j + 1;
        last = min(LCP(rank[rev(i+j-1)], rank[rev(i+j+j+m-1)]), j-1); // 向左
    }
}

總結

BZOJ 2119 是「後綴數組 + 區間 LCP + 枚舉長度」的高難度綜合題。核心洞察：差分消除絕對值 → ABA 結構轉化為等長公共前綴/後綴 → SA+RMQ 高效查詢。掌握此模板可解決 BZOJ 2119、Codeforces 子串周期性問題。