HDOJ 4455 Substrings：遞推 + 樹狀數組統計區間不同元素數

問題

給定長度 n（≤ 10⁶）數組，Q（≤ 10⁴）次查詢：區間長度 w 下所有子區間不同元素個數之和。

遞推公式推導

設 dp[w] 為長度 w 的答案。
pre[i] = i 向左最近相同元素距離。
考慮從 w−1 擴展到 w：新增右端點貢獻，減去左端點移出貢獻。
利用樹狀數組維護 pre 值的頻次，O(log n) 更新查詢。

關鍵代碼

// 預處理 pre 與 spre（pre 值頻次）
for (int i = n; i >= 1; --i) {
    int x = a[i];
    if (last[x] == -1) last[x] = i;
    else { spre[last[x] - i]++; pre[last[x]] = last[x] - i; last[x] = i; }
}
// BIT 維護 spre
// 遞推 dp[w]
for (int w = 2; w <= n; ++w) {
    int delay = sumBIT(1, w-2) + ...; // 區間外元素貢獻
    dp[w] = dp[w-1] + A - B; // 具體公式見代碼
}

完整代碼結構

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
int a[MAXN], pre[MAXN], spre[MAXN], last[MAXN];
ll dp[MAXN], bit[MAXN];
int lowbit(int x) { return x & -x; }
void addBIT(int i, int v) { for (; i < MAXN; i += lowbit(i)) bit[i] += v; }
ll sumBIT(int i) { ll r=0; for(;i>0;i-=lowbit(i)) r+=bit[i]; return r; }
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        // 初始化 last, pre, spre
        // 建 BIT
        // 遞推 dp
        int Q; cin >> Q;
        while (Q--) { int w; cin >> w; cout << dp[w] << '\n'; }
    }
    return 0;
}

複雜度

預處理 O(n)；遞推 O(n log n)；查詢 O(1)。
記憶體 O(n)，需用 long long 存儲答案。