HDU 5400 Arithmetic Sequence：雙公差等差區間計數

題目大意

給定序列 a[1…n] 及兩公差 d1, d2。求區間 [l, r] 滿足以下任一條件的個數：

1. 整個區間是公差為 d1 或 d2 的等差數列。
2. 存在 i（l ≤ i ≤ r），使 [l, i] 公差 d1，[i, r] 公差 d2。

n ≤ 10⁵，需 O(n) 或 O(n log n) 算法。

線性掃描 + 狀態機

維護左右指針 L, R 表示當前合法區間起點。
狀態 state = 1 表示當前在 d1 段，2 表示在 d2 段。
掃描 i = 2…n，計算 diff = a[i] − a[i−1]。

狀態轉移

• state == 1：
  • diff == d1：R = i，答案 += R−L+1。
  • diff == d2：state = 2，R = i，答案 += R−L+1。
  • 否則：L = R = i，答案++（單元素區間）。
• state == 2：
  • diff == d2：R = i，答案 += R−L+1。
  • diff == d1：不允許 d1 出現在 d2 之後 → 新區間起點 L = i−1，R = i，state = 1，答案 += 2。
  • 否則：L = i，答案++。

完整代碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, d1, d2;
    while (cin >> n >> d1 >> d2) {
        vector<ll> a(n+1), diff(n+1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 2; i <= n; ++i) diff[i] = a[i] - a[i-1];
        ll ans = n; // 長度 1 的區間
        int L = 1, R = 1, state = 1; // 1:d1, 2:d2
        for (int i = 2; i <= n; ++i) {
            if (state == 1) {
                if (diff[i] == d1) { R = i; ans += R - L + 1; }
                else if (diff[i] == d2) { state = 2; R = i; ans += R - L + 1; }
                else { L = R = i; ans++; }
            } else { // state == 2
                if (diff[i] == d2) { R = i; ans += R - L + 1; }
                else if (diff[i] == d1) { state = 1; L = i-1; R = i; ans += 2; }
                else { L = i; ans++; }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(n) 時間，O(n) 空間。單次掃描即得答案。