伪代码理解
题目定义了一个函数 f(l, r, s)，用于计算数组 s从索引 l 到 r 的子数组的“权值”。计算方式如下：
遍历子数组中的每个元素，维护一个集合记录已出现的不同元素，对于每个位置，将“到当前位置为止出现的不同元素个数”累加到总和中，返回这个总和。我们需要计算所有非空子数组的权值之和。
最直接的思路是枚举所有子数组，对于每个子数组都调用 f 函数计算权值，时间复杂度：O(n³)（三层循环），对于 n ≤ 10⁵ 完全不可行
高效解法思路
核心观察：我们不能计算每个子数组，但可以计算每个元素对总答案的贡献。
对于一个元素 a[i]：
它只在子数组中首次出现时才会产生贡献，贡献的大小取决于：它能影响多少个子数组位置
推导过程
- 贡献条件分析
元素 a[i]在子数组 [l, r]中能产生贡献的条件是：
-
l ≤ i ≤ r
-
a[i]在 [l, i]区间内是首次出现
这意味着 l > lastPos[a[i]]（ lastPos[a[i]]是 a[i]上一次出现的位置）
- 贡献大小分析
-
如果 a[i]在子数组 [l, r]中首次出现，那么：
-
它会使得 distinct(l, i)增加1
-
它会使得 distinct(l, i+1)增加1
-
...
-
它会使得 distinct(l, r)增加1
所以，对于固定的 l 和 r，a[i] 的贡献是 (r - i + 1)
3. 数学公式推导
设 last是 a[i]上一次出现的位置（若没有则 last = -1）
-
有效的起始位置 l数量：cnt = i - last
-
对于每个 l，有效的右端点 r范围：i≤ r≤ n-1
-
对于固定的 l，a[i]的总贡献：1 + 2 + ... + (n-i) = (n-i)*(n-i+1)/2
-
a[i]的总贡献：cnt * (n-i)*(n-i+1)/2
4. 最终公式 ans=
其中 lastPos[a[i]] 是 a[i] 在位置 i之前最后一次出现的位置（若没有则为 -1）设 lastPos[a[i]] = -1，这样：i−(−1)=i+1，恰好等于有效起始位置的数量
由此得出解码思路，AC码如下：
……省略头文件
//头文件有#define int long long 为了减少代码量没复制头文件
void solve() {
int n,i;
cin >> n;
vi a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
unordered_map<int, int> pos;
int ans = 0;
for (i = 0; i < n; i++) {
int last = (pos.count(a[i])) ? pos[a[i]] : -1;
int cnt = i - last;
int len = n - i;
ans += 1LL * cnt * len * (len + 1) / 2;
pos[a[i]] = i;
}
cout << ans << endl;
}
signed main() {
//vector<vector<int>>a(n,vector<int>(m)); 二维构造
//cout << fixed << setprecision(10); 固定小数输出
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
如有错误感谢指出和纠正！
京公网安备 11010502036488号