HDU 5400 Arithmetic Sequence 另解：暴力枚舉優化

另一視角：枚舉分界點

對每個可能的分界點 i（1 ≤ i ≤ n），將其作為 d1 段結束、d2 段開始的位置。
預處理：

• up[i]：以 i 為右端點、公差 d1 的最長等差段左端點。
• down[i]：以 i 為左端點、公差 d2 的最長等差段右端點。

則合法區間 [l, r] 滿足：存在 i 使 l ≥ up[i] 且 r ≤ down[i]。
用雙指針或二分統計所有 (l, r) 對數。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 100010;
ll a[MAXN];
int up[MAXN], down[MAXN];
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, d1, d2;
    while (cin >> n >> d1 >> d2) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        // 預處理 up
        up[1] = 1;
        for (int i = 2; i <= n; ++i)
            up[i] = (a[i] - a[i-1] == d1) ? up[i-1] : i;
        // 預處理 down
        down[n] = n;
        for (int i = n-1; i >= 1; --i)
            down[i] = (a[i+1] - a[i] == d2) ? down[i+1] : i;
        ll ans = 0;
        // 單公差段
        for (int i = 1; i <= n; ++i) ans += i - up[i] + 1;
        for (int i = 1; i <= n; ++i) ans += down[i] - i + 1;
        if (d1 == d2) { cout << ans << '\n'; continue; }
        // 雙公差段：枚舉分界 i
        for (int i = 1; i < n; ++i) {
            int L = up[i], R = down[i+1];
            ans += (ll)(i - L + 1) * (R - i);
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(n) 預處理 + O(n) 統計，總 O(n)。