HDU 5172 GTY 的好友查詢：線段樹離線處理區間全排列判定

問題背景

給定 n 個數字的序列和 m 個查詢，每個查詢詢問區間 [l, r] 內的數字是否恰好構成 1 到 r-l+1 的一個排列。數據範圍高達 10^6，需高效算法。

核心洞察

區間為全排列的充要條件：

1. 區間元素和等於 1+2+...+(r-l+1) = (r-l+1)(r-l+2)/2
2. 區間內無重複元素

線段樹離線解法

預處理每個位置 i 的「左側最近相同值位置」pre[i]。構建線段樹維護區間最大 pre 值。查詢時，若區間最大 pre 值 < l，則說明區間內無重複值（因為所有重複值的前驅都在 l 之前）。結合前綴和檢查元素和，即可 O(log n) 回答每個查詢。

關鍵代碼片段（C++）

// 線段樹維護區間最大前驅位置
void update(int x, int c, int l, int r, int rs) {
    if (l == r) { sum[rs] = c; return; }
    int mid = (l + r) >> 1;
    if (x <= mid) update(x, c, l, mid, rs << 1);
    else update(x, c, mid + 1, r, rs << 1 | 1);
    sum[rs] = max(sum[rs << 1], sum[rs << 1 | 1]);
}

int query(int x, int y, int l, int r, int rs) {
    if (x <= l && r <= y) return sum[rs];
    int mid = (l + r) >> 1, res = 0;
    if (x <= mid) res = max(res, query(x, y, l, mid, rs << 1));
    if (y > mid) res = max(res, query(x, y, mid + 1, r, rs << 1 | 1));
    return res;
}

// 主邏輯
while (m--) {
    scanf("%d%d", &x, &y);
    long long expected = 1LL * (y - x + 1) * (y - x + 2) / 2;
    if (s[y] - s[x - 1] == expected && query(x, y, 1, n, 1) < x)
        puts("YES");
    else
        puts("NO");
}

複雜度分析

• 預處理：O(n log n)
• 每查詢：O(log n)
• 總體：O((n + m) log n)，滿足 10^6 規模

避坑指南

• 使用 long long 存儲前綴和防止溢出
• 線段樹數組大小開 4*n
• 離線處理需重置全局數組
• 輸入輸出用 scanf/printf 加速

此題展示了線段樹在區間去重問題中的經典應用，結合數學性質巧妙轉化查詢條件。