CF1789C 题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-27 14:02:55

题外话

本题解作者赛时由于漏了一个 -1，调了 1h，导致的分数损失约为 350，排名损失约为 600，最后还是把小号送上了 Specialist。

为了方便表示，设 $f(i,j)$ 为 $A_i$ 与 $A_j$ 不同元素总数。

暴力计算 $\sum_{i=1}^{n} \sum_{j=0}^{i-1} f(i,j)$。
复杂度 $O(n^3)$。

想想有没有什么优化。

可以看到每次生成新序列，只从上一个序列修改一个数字，那就启发我们每个序列的答案可以从上一个序列转移，现在把它表示出来：设 $dp_i$ 为 $\sum_{j=0}^{i-1} f(i,j)$。

设本次修改得到的序列为 $A_i$，现在分类讨论一下。

如果本次修改的元素，新值等于旧值，即没有改变原序列，那么 $\sum_{j=0}^{i-2} f(i,j) = dp_{i-1}$，而 $f(i,j-1)$ 显然等于 $n$，即 $dp_i = dp_{i-1} + n$。
如果本次修改的元素，新值不等于旧值，即改变了原序列，这时我们可以先假设本次修改没有改变原序列，先使用情况 $1$ 的答案，然后再根据修改的元素调整答案。我们可以先减去被改掉的旧值的贡献，再加上新值的贡献。而这个东西怎么计算呢，显然只需要分别统计对于所有的 $0 \le j \le i-1$，有多少个 $A_j$ 没有旧值，有多少个 $A_j$ 没有新值。

至此，做法基本确定。

但是问题来了，怎么快速统计每个元素没有出现在多少个序列里，它可以转化为快速统计每个元素出现在了多少个序列里。

由于没有后效性，即对于每个 $dp_i$，只有 $0$ 到 $i-1$ 会进行转移，所以这个统计数值也可以动态转移。

显然不能每增加一个序列就去修改所有的元素出现次数，我们发现修改操作每次只是让一个元素消失，让另一个元素出现，我们可以让它自己改。

也就是设 $start_i$ 表示第 $i$ 种元素在第几个序列开始出现，如果为 $-1$ 代表没出现过；$end_i$ 表示第 $i$ 种元素在第几个序列最后一次出现，如果为 $-1$ 代表一直到现在还没有消失。

第 $i$ 种元素总出现次数即 $end_i - start_i + 1$。

修改的时候，如果是让某元素消失，直接标记上 $end = i-1$ 就行了。

如果是让某元素出现，那分讨一下。

之前没出现过，标记上 $start = i$，$end = -1$。
之前出现过，那还得计算之前的贡献，然后再算上现在的贡献，同时因为从现在开始这个元素又重新出现了，$end$ 必须等于 $-1$，而为了使答案正确，我么可以让 $start = i-(end - start + 1) +1 - 1 = i-(end-start+1)$，形象地理解，这是把之前这个元素出现区间般过来，然后把右端点删掉。