離散化處理

// 複製排序去重
sort(val+1, val+n+1);
int m = unique(val+1, val+n+1) - val - 1;
// 查找離散化索引
int get_id(int x) { return lower_bound(val+1, val+m+1, x) - val; }
// 查詢區間 [L, R] 對應的離散索引範圍
int L_id = get_id(a[i] - d);
int R_id = get_id(a[i] + d); // 注意 upper_bound 邊界

核心代碼

const int MOD = 9901;
int bit[100010]; // 樹狀數組

void add(int idx, int val) {
    for (; idx <= m; idx += idx & -idx) {
        bit[idx] = (bit[idx] + val) % MOD;
    }
}

int query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx) {
        res = (res + bit[idx]) % MOD;
    }
    return res;
}

int main() {
    int n, d;
    while (~scanf("%d%d", &n, &d)) {
        // 讀入、離散化...
        memset(bit, 0, sizeof(bit));
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int id = get_id(a[i]);
            int L = get_id(a[i] - d);
            int R = upper_bound(val+1, val+m+1, a[i]+d) - val - 1;
            int sum = (query(R) - query(L-1) + MOD) % MOD;
            int dp = (sum + 1) % MOD; // +1 為單元素子序列
            add(id, dp);
            ans = (ans + dp) % MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}

關鍵細節

1. 離散化邊界：a[i]+d 可能不在值域中，需用 upper_bound 找 ≤ 該值的最大索引。
2. 模運算：減法需 +MOD 再 %MOD 避免負數。
3. 多測試用例：每案例重置 bit、val、m。
4. 值域大小：離散化後 m ≤ n，樹狀數組大小開 n+5 即可。

複雜度

• 時間：O(n log n) 排序 + O(n log n) DP，總 O(n log n)。
• 空間：O(n)。

總結

HDU 3450 是「DP + 數據結構優化」的經典範例。當 DP 轉移為「區間和查詢」時，樹狀數組/線段樹可將 O(n²) 降為 O(n log n)。關鍵步驟：

1. 定義 DP 狀態與轉移方程。
2. 識別轉移中的區間查詢模式。
3. 離散化將值域映射為索引。
4. 樹狀數組維護前綴和，支持單點更新、區間查詢。

此模板廣泛適用於「受值域約束的子序列/子數組計數」問題。