CF1789C 题解

· · 题解

题外话

本题解作者赛时由于漏了一个 -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，现在分类讨论一下。

  1. 如果本次修改的元素，新值等于旧值，即没有改变原序列，那么 \sum_{j=0}^{i-2} f(i,j) = dp_{i-1}，而 f(i,j-1) 显然等于 n，即 dp_i = dp_{i-1} + n。
  2. 如果本次修改的元素，新值不等于旧值，即改变了原序列，这时我们可以先假设本次修改没有改变原序列，先使用情况 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 就行了。

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

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

CF 提交记录