【题解】abc371_e I Hate Sigma Problems

Statement

给定一个长度为 $n$ 的数组 $a$，定义函数 $f(l, r)$ 表示区间 $(a_l, a_{l + 1}, \ldots a_r)$ 中不同值的个数，求：

$$\sum_{i = 1}^n \sum_{j = i}^n f(i, j)$$

的值，其中 $1 \le \forall a_i \le n \le 2 \times 10 ^ 5$。

Solution

一道代码量极少的思维好题。

遇到这种区间求和问题，第一步先考虑找到所有区间之间的共同点，将原本 $O(n^2)$ 的暴力转化成 $O(n)$ 的算法，在这里先考虑暴力：

1
2
3
4
5
6
7
8

auto add = [] (int x) { if (++ cnt[x] == 1) cur ++; };
for (int i = 1; i <= n; i ++)
{
    memset(cnt, 0, sizeof cnt), cur = 0;
    for (int j = i; j <= n; j ++)
        add(a[j]), ans += cur;
}
cout << ans << '\n';

不难发现，如果区间中没有重复的数，那么贡献就是区间的长度，如果存在相同的数，那么这个数的贡献仍旧为 $1$，为了方便处理，我们钦定每个区间出现第一次的数存在贡献，定义数组 $g$，其中 $g_i$ 表示第 $i$ 个数在这 $n^2$ 个区间中所作出的总贡献，答案即为 $\textstyle{\sum_{i = 1} ^ n g_i}$。

那么如何求出每个元素作为区间第一个数出现的总贡献呢？先抛开这个问题不谈，思考每个下标在 $n^2$ 个区间中出现的次数，通过对左边界 $l$ 进行讨论，不难发现，对于第 $i$ 个数，它前面有 $i - 1$ 个数，而这些数作为左边界时，右边界可以取 $i, i + 1, i + 2, \ldots, n$ 一共 $n - i + 1$ 种取值，当 $l = i$ 时，同样也有 $n - i + 1$ 种~~（这不是废话么）~~。因此对在数组中第一次出现的数，它所做出的贡献为 $i \times (n - i + 1)$。

接下来尝试把结论推广至重复出现的数，对于一个数 $a_i$，假设它上一次出现是在 $j$，那么他可以存在贡献当且仅当 $l \in [j + 1, i]$，用同样的方法计算它在合法区间中的次数，不难得出贡献为 $(i - j + 1) \times (n - i + 1)$（本质上和上式一样的）。

因此做法十分简单，首先预处理出每一个元素上一次出现的下标 $Lpos_i$（第一次出现则为 $0$），答案即为：

$$ans \gets \sum_{i = 1}^n (i - lpos_i) \times {n - i + 1}$$

Code

1
2
3
4
5
6
7
8
9

signed main()    // 记得开 long long
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) L[i] = cur[a[i]], cur[a[i]] = i;
    for (int i = 1; i <= n; i ++) ans += (i - L[i]) * (n - i + 1);
    cout << ans << '\n';
    return 0;
}