BZOJ 4358 perm 詳解：區間最長值域連續段長度查詢

題目大意

給定長度 n 的排列 P[1..n]，m 次詢問：區間 [l, r] 中，最長的值域連續段長度。值域連續段指：下標集合 {i1, i2, ..., ik} ⊆ [l, r]，對應值 {P[i1], ..., P[ik]} 恰構成連續整數區間（如 {3,1,2} 值域為 [1,3]）。

範例：P = [3,1,7,2,5,8,6,4]

• 詢問 [1,4]：子陣列 {3,1,7,2}，最長值域連續段為 {3,1,2}（值域 [1,3]），長度 3
• 詢問 [5,8]：{5,8,6,4}，最長為 {5,6,4}（值域 [4,6]），長度 3
• 詢問 [1,7]：{3,1,7,2,5,8,6}，最長為 {5,7,8,6}（值域 [5,8]），長度 4

核心觀察

對於排列，區間 [l, r] 內的值域連續段等價於：最大值 - 最小值 = 右端點 - 左端點 的子區間。即找 l ≤ L ≤ R ≤ r 使 max(P[L..R]) - min(P[L..R]) = R - L，最大化 R - L + 1。

解法：莫隊算法 + 启發式合併 / 線段樹維護

本題標準解法為莫隊算法離線處理詢問，配合數據結構維護當前區間的最長值域連續段。關鍵難點在於區間擴展/縮減時如何高效更新答案。

莫隊算法框架

• 分塊大小 B = sqrt(n)
• 詢問按 (l/B, r) 排序
• 雙指針維護當前區間 [L, R]

區間擴展時的信息維護

需維護當前區間內：

1. 值到位置的映射 pos[val]
2. 以某值為端點的最長連續段長度

具體可用並查集類結構或線段樹維護「值域連續段」信息。當加入值 x 時，檢查 x-1 和 x+1 是否已在區間內，若在則合併段。

啟發式合併優化

維護每個連續段的：

• 最小值、最大值
• 長度
• 左右鄰段指針

合併時總是將小段併入大段，時間複雜度 O(n log n)。

代碼框架（核心邏輯）

struct Segment {
    int minVal, maxVal, len;
    Segment *left, *right;
};

Segment* segments[MAXN];  // 值到段的映射

void addValue(int x) {
    Segment* cur = new Segment{x, x, 1, nullptr, nullptr};
    segments[x] = cur;
    
    // 嘗試與左鄰段合併
    if (x > 1 && segments[x-1]) {
        Segment* L = findRoot(segments[x-1]);
        if (L->maxVal == x-1) merge(L, cur);
    }
    // 嘗試與右鄰段合併
    if (x < n && segments[x+1]) {
        Segment* R = findRoot(segments[x+1]);
        if (R->minVal == x+1) merge(cur, R);
    }
    // 更新全局最大長度
    ans = max(ans, cur->len);
}

複雜度分析

• 莫隊排序：O(m log m)
• 指針移動總次數：O(n sqrt(m))
• 每次 add/remove：O(α(n)) 或 O(log n)
• 總體：O((n + m) sqrt(n) log n) 或優化至 O(n log n + m sqrt(n))

總結

BZOJ 4358 是莫隊算法配合區間值域連續段維護的經典題目。核心難點在於：

1. 正確理解「值域連續段」在排列中的等價條件
2. 設計高效的區間擴展/縮減時的段合併/分裂邏輯
3. 啟發式合併或線段樹優化更新複雜度

此類問題常見於「區間最長連續子序列」變體，掌握莫隊 + 數據結構維護模式對解決離線區間查詢極有幫助。