HDU 5183 題解：交錯前綴和與集合查找 O(n log n) 解法

題目大意

給定序列 a[1..n] 和整數 k。定義 NP-Sum(i, j) = a[i] - a[i+1] + a[i+2] - ... + (-1)^(j-i) a[j] (交錯和)。問是否存在 i ≤ j 使 NP-Sum(i, j) = k。

數學轉換：後綴交錯和

定義後綴交錯和 S[i] (從右向左，以加號起始)：

S[i] = a[i] - a[i+1] + a[i+2] - ... ± a[n]

則區間交錯和可表示為：

• 若 i 為奇數：NP-Sum(i, j) = S[i] - S[j+1]
• 若 i 為偶數：NP-Sum(i, j) = -S[i] + S[j+1]

證明：交錯和本質是前綴和的差，符號取決於起始位置奇偶性。

演算法邏輯

1. 從右向左計算 S[i] 並存入集合。
2. 對於當前 i：
   • 奇數 i：查找集合中是否存在 S[i] - k (對應 S[j+1])
   • 偶數 i：查找集合中是否存在 S[i] + k
3. 將 S[i] 加入集合供下一輪 (即 j+1) 使用。

完整 C++ 程式碼

#include 
using namespace std;
using ll = long long;

inline ll read_ll() {
    char ch; ll f=1, x=0;
    while ((ch=getchar())!='-' && (ch<'0'||ch>'9'));
    if (ch=='-') f=-1; else x=ch-'0';
    while ((ch=getchar())>='0'&&ch<='9') x=x*10+ch-'0';
    return f*x;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int n; ll k;
        scanf("%d %lld", &n, &k);
        vector a(n+2);
        for (int i = 1; i <= n; i++) a[i] = read_ll();
        
        unordered_set seen;
        seen.reserve(n * 2);
        seen.max_load_factor(0.7);
        seen.insert(0);  // S[n+1] = 0
        
        ll suffix = 0;
        bool found = false;
        for (int i = n; i >= 1; i--) {
            if (i & 1) suffix -= a[i];  // 奇數位減
            else       suffix += a[i];  // 偶數位加
            
            if (i & 1) {  // i 為奇數
                if (seen.count(suffix - k)) { found = true; break; }
            } else {      // i 為偶數
                if (seen.count(suffix + k)) { found = true; break; }
            }
            seen.insert(suffix);
        }
        
        printf("Case #%d: %s\n", cas, found ? "Yes." : "No.");
    }
    return 0;
}

關鍵優化點

複雜度分析

• 時間：O(n) 期望 (雜湊表平均 O(1))，最壞 O(n²) 但極難構造。
• 空間：O(n) 存儲雜湊表。

常見錯誤

• 符號搞反：必須嚴格區分奇數/偶數起始位置的符號規則。
• 忘記插入 0：導致區間延伸到陣列末尾的情況漏判。
• 使用 set (紅黑樹) 導致 O(n log n) 可能 TLE，大數據必須 unordered_set。

核心技巧：交錯和轉換為後綴和差分，配合奇偶性分類討論，將區間查詢轉為單點查找集合。這是處理「帶符號區間和」問題的通用模板。