ZOJ 3872 Beauty of Array：子數組不同元素和的總和（O(N) 數學解法）

問題重述

數組 A[1..N]（N≤10⁵），定義子數組「美麗值」為其中**不同元素之和**。求所有連續子數組美麗值之和。

核心洞察：貢獻法 + 間隔扣除

對每個值 v，設其出現位置為 p₁ < p₂ < … < p_k。
總子數組數 = N(N+1)/2。
若在首尾添加虛擬位置 0 和 N+1，則相鄰兩次出現之間的區間（不含端點）內的子數組**完全不包含** v。
不含 v 的子數組數 = Σ C(gap, 2)，其中 gap 為相鄰出現位置差 − 1。
v 的貢獻 = v × (總子數組數 − 不含 v 的子數組數)。

算法流程

1. 離散化/哈希記錄每個值的所有出現位置（按序）。
2. 對每個值遍歷其位置向量，累加間隔貢獻。
3. 總答案對 2⁶⁴ 自然溢出（用 `unsigned long long`）或取模（題目無模數要求）。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector a(n+1);
        vector> pos(1000001);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            pos[a[i]].push_back(i);
        }
        ull ans = 0;
        ull total = 1ULL * n * (n + 1) / 2;
        for (int v = 1; v <= 1000000; ++v) {
            if (pos[v].empty()) continue;
            ull without = 0;
            int last = 0;
            for (int p : pos[v]) {
                int gap = p - last - 1;
                without += 1ULL * gap * (gap + 1) / 2;
                last = p;
            }
            without += 1ULL * (n - last) * (n - last + 1) / 2;
            ans += 1ULL * v * (total - without);
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(N + V)，V = max(A_i) ≤ 10⁶，線性通過。