题目描述

难度分:$981$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

定义$f(i,j)$为连续子数组$a[i]$~$a[j]$中的不同元素个数。

输出所有$f(i,j)$之和，其中$i \leq j$。

输入样例$1$

3
1 2 2

输出样例$1$

8

输入样例$2$

9
5 4 2 2 3 2 4 4 1

输出样例$2$

111

算法

贡献法

比较经典的贡献法求答案，每个子数组中的每一个值第一次出现才能对答案产生贡献。因此，遍历$a[i]$，假设它上一次出现的位置在$last[a[i]]$，那么$a[i]$能够为左边界在$(last[a[i]],i]$，右边界在$[i,n]$的子数组产生贡献，因为它在这些数组中，是第一个出现的$a[i]$。所以$\Sigma_{i=1}^{n}(i-last[a[i]]) \times (n-i+1)$就是最终答案。

复杂度分析

时间复杂度

遍历一遍数组$a$就能求出答案，时间复杂度为$O(n)$。

空间复杂度

需要一个数组$last$来记录$a[i]$上一次出现的位置，考虑到$a[i] \in [1,n]$，$last$的空间也是线性的。整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, a[N], last[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        last[i] = 0;
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        ans += (i - last[a[i]]) * (n - i + 1LL);
        last[a[i]] = i;
    }
    printf("%lld\n", ans);
    return 0;
}