HDU 2836 Traversal：線段樹 + 離散化 + DP 計數合法子序列

題目大意

給定長度 n 的數列 a[1..n] 與閾值 h。求：相鄰元素差值絕對值不超過 h 的非空子序列個數，結果對 9901 取模。

核心思路：DP + 線段樹優化區間查詢

動態規劃定義

d[i]：以 a[i] 結尾的合法子序列個數（包含單元素子序列）。

轉移：對所有 j < i，若 |a[j] - a[i]| <= h，則 d[i] += d[j]。初始 d[i] = 1（單元素子序列）。

條件等價於：a[i] - h <= a[j] <= a[i] + h。需快速查詢值域區間 [L, R] 內所有 d[j] 之和。

離散化 + 線段樹

1. 收集所有 a[i]，排序去重得到離散化陣列 b[]，長度 len。
2. 線段樹維護離散化值域上 d 值的前綴和。節點儲存區間和，支援單點更新、區間查詢，均為 O(log len)。
3. 處理順序：i = 1..n
   • 計算查詢區間：l = lower_bound(b, a[i]-h)，r = upper_bound(b, a[i]+h) - 1。
   • 查詢區間和 sum = query(l, r)，d[i] = (1 + sum) % MOD。
   • 更新答案 ans = (ans + d[i] - 1) % MOD（扣除單元素）。
   • 單點更新 pos = lower_bound(b, a[i])，update(pos, d[i])。

關鍵實現細節

• 模數 MOD = 9901，所有加法運算需取模。
• 線段樹陣列大小 maxn << 2。建樹初始化為 0。
• lower_bound 回傳第一個 >= val 的位置（1-based 索引）；upper_bound 回傳第一個 > val 的位置，減 1 得 <= val 的最大位置。
• 若 l > r 則查詢結果為 0。

完整程式碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 9901;
const int maxn = 100000 + 10;
int n, h;
int a[maxn], b[maxn];
int sum[maxn << 2], d[maxn];

inline void add(int& a, int b) { a += b; if (a >= MOD) a %= MOD; }

void pushup(int o) { add(sum[o], sum[o<<1] + sum[o<<1|1]); }

void build(int l, int r, int o) {
    sum[o] = 0;
    if (l == r) return;
    int m = (l + r) >> 1;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
}

void update(int L, int R, int v, int l, int r, int o) {
    if (L <= l && r <= R) { add(sum[o], v); return; }
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, v, l, m, o<<1);
    if (m < R) update(L, R, v, m+1, r, o<<1|1);
    pushup(o);
}

int query(int L, int R, int l, int r, int o) {
    if (L <= l && r <= R) return sum[o];
    int m = (l + r) >> 1, ans = 0;
    if (L <= m) add(ans, query(L, R, l, m, o<<1));
    if (m < R) add(ans, query(L, R, m+1, r, o<<1|1));
    return ans;
}

int main() {
    while (~scanf("%d%d", &n, &h)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            b[i-1] = a[i];
        }
        sort(b, b+n);
        int len = unique(b, b+n) - b;
        build(1, len, 1);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int l = lower_bound(b, b+len, a[i]-h) - b + 1;
            int r = upper_bound(b, b+len, a[i]+h) - b;
            int pos = lower_bound(b, b+len, a[i]) - b + 1;
            d[i] = 1;
            add(d[i], query(l, r, 1, len, 1));
            add(ans, d[i] - 1);
            update(pos, pos, d[i], 1, len, 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度分析

• 離散化排序：O(n log n)
• 主迴圈 n 次，每次 2 次查詢 + 1 次更新：O(n log n)
• 總時間 O(n log n)，空間 O(n)，滿足 n <= 100000。