HDU 5247 找連續數：雙指針 + 訪問標記 O(n·k) 解法

問題描述

給定長度 n ≤ 10⁴ 的無序數組，m ≤ 1000 次查詢。每次查詢給定 k ≤ 1000，詢問有多少個長度為 k 的連續子區間，其元素排序後形成連續整數序列（如 {3,2,4} 排序後為 2,3,4）。

連續序列判斷條件

區間 [L,R] 長度 len = R-L+1，元素排序後連續 ⇔ 最大值 - 最小值 + 1 = len 且所有元素互不相同。
即：max - min + 1 == len && 無重複。

優化思路：固定左端點擴展右端點 + 訪問標記剪枝

• 外層循環固定左端點 i。
• 內層循環擴展右端點 j，維護 max、min、vis[]（標記值是否出現）。
• 若 a[j] 已出現（vis[a[j]]），直接 break：後續擴展必含重複元素，不可能連續。
• 若 max - min + 1 == j-i+1，則 ans[len]++。

打表預處理

因查詢 k ≤ 1000，且 n ≤ 10⁴，預先計算所有長度 1~1000 的合法區間個數存入 ans[k]，查詢 O(1) 回答。

代碼實現

#include 
using namespace std;
const int MAXN = 10010;
const int MAXV = 100010; // 值域較大，但 n 小，可用 unordered_map 或開大數組
int a[MAXN], ans[MAXN];
int vis[MAXV];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    memset(ans, 0, sizeof(ans));
    for (int i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis)); // 每個左端點重置訪問標記
        int mx = 0, mn = INT_MAX;
        for (int j = i; j <= n; ++j) {
            mx = max(mx, a[j]);
            mn = min(mn, a[j]);
            int len = j - i + 1;
            if (vis[a[j]]) break; // 遇到重複，剪枝
            vis[a[j]] = 1;
            if (mx - mn + 1 == len) ans[len]++;
        }
    }
    
    cout << "Case #1:\n";
    while (m--) {
        int k; cin >> k;
        cout << ans[k] << '\n';
    }
    return 0;
}

複雜度分析

• 預處理：外層 n，內層最多 n，但 break 剪枝極大減少實際迭代。最壞 O(n²)，實際遠小。
• 查詢：O(1)。
• 空間：O(n + maxV)。

關鍵優化點

1. vis 陣列重置：用 timer 技巧避免 memset：vis[val] == timer 表示已訪問，每輪 ++timer。
2. 值域大：若 a[i] ≤ 2³¹，vis 用 unordered_map 或 vector + timer（離散化）。
3. 長度限制：內層循環可在 len > 1000 時 break，因查詢 k ≤ 1000。

總結

本題是「區間連續性判斷 + 多查詢離線打表」的經典結合。核心技巧：雙指針擴展 + 訪問標記剪枝重複 + 預計算所有長度答案。理解「max-min+1==len 且無重複 ⇔ 連續」的等價條件是解題關鍵。