问题分析

问题描述

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，对于每个 $d = 1, 2, \dots, n$，需要计算所有长度为 $d$ 的连续子区间中不同元素个数的总和 $S_d$。

关键观察

1. 问题规模：$n$ 最大为 $2 \times 10^5$，需要高效算法
2. 暴力不可行：直接枚举所有区间的时间复杂度为 $O(n^2)$，无法通过
3. 核心难点：需要同时计算所有区间长度的答案

算法思路

核心思想：贡献法

考虑每个位置 $i$ 上的元素 $a_i$ 对答案的贡献。一个元素在区间 $[l, r]$ 中有贡献当且仅当：

• 区间包含位置 $i$
• 该区间中 $a_i$ 是第一次出现（即区间不包含该元素之前出现的位置）

数学建模

设 $prev[i]$ 表示 $a_i$ 前一次出现的位置（不存在则为 $0$），则位置 $i$ 的元素能贡献的区间需要满足：

• $l \leq i \leq r$
• $l > prev[i]$
• $r - l + 1 = d$

对于固定的 $i$，它能贡献的区间长度 $d$ 的范围是：

• 最小长度：$1$
• 最大长度：$i - prev[i]$

差分数组技巧

使用差分数组来高效记录每个区间长度的贡献：

• 对于每个位置 $i$，在区间 $[1, i - prev[i]]$ 上给 $S_d$ 加 $1$
• 通过差分数组实现区间加操作
• 最后通过前缀和恢复实际的 $S_d$ 值

算法步骤

步骤1：预处理前驱位置

使用哈希表记录每个数值最后出现的位置，计算每个位置 $i$ 的前驱位置 $prev[i]$。

步骤2：计算贡献范围

对于每个位置 $i$：

• 计算最大贡献长度 $L = i - prev[i]$
• 在差分数组中标记区间 $[1, L]$ 的贡献

步骤3：计算最终答案

通过对差分数组求前缀和，得到每个 $S_d$ 的值。

复杂度分析

• 时间复杂度：$O(n)$

  • 预处理前驱位置：$O(n)$
  • 计算贡献：$O(n)$
  • 前缀和计算：$O(n)$

• 空间复杂度：$O(n)$

  • 存储前驱位置数组：$O(n)$
  • 差分数组：$O(n)$
  • 哈希表：$O(n)$

正确性证明

贡献完整性

每个区间中，每个不同的元素恰好有一个位置是它在区间中的第一次出现，因此：

• 区间的不同元素个数等于该区间中有贡献的位置数
• 每个有贡献的位置恰好贡献 $1$ 到该区间的答案中

贡献不重不漏

通过 $prev[i]$ 确保：

• 每个元素只在合适的区间长度范围内贡献
• 不会重复计算同一元素在区间中的多次出现

特殊情况处理

边界情况

1. $prev[i] = 0$：元素第一次出现，能贡献所有包含它的区间
2. 重复元素密集：通过 $prev[i]$ 正确处理重复元素的贡献范围
3. 所有元素相同：每个位置的最大贡献长度递减

数值范围

• $a_i$ 最大到 $10^9$，必须使用哈希表而非数组记录位置
• 答案可能很大，需要使用足够大的整数类型

优化技巧

空间优化

• 可以省略显式的 $prev$ 数组，在遍历时直接计算贡献
• 差分数组只需要 $n + 2$ 的大小

实现优化

• 使用高效的哈希表实现
• 避免不必要的内存分配和拷贝

算法优势

1. 高效性：$O(n)$ 时间复杂度处理 $2 \times 10^5$ 规模数据
2. 简洁性：算法思路清晰，实现相对简单
3. 通用性：适用于任意数值范围的输入数据
4. 最优性：时间复杂度达到理论下界

总结

本题展示了组合计数问题中贡献法的强大威力。通过将复杂的区间计数问题转化为简单的元素贡献分析，再结合差分技巧实现高效计算，最终在 $O(n)$ 时间内解决了看似需要 $O(n^2)$ 的问题。

关键洞察在于认识到：一个元素在区间中有贡献当且仅当它是该区间中该种元素的第一次出现。这个深刻的观察使得我们能够将问题分解，从而设计出高效的算法。

该解法不仅在理论上优美，在实际应用中也具有很好的性能表现，能够处理大规模数据输入。