题解 P5072 【[Ynoi2015] 盼君勿忘】

· · 题解

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。————世界上最幸福的女孩

珂朵莉，要一直幸福哦。

第一道珂朵莉相关 \text{Ynoi} 祭。

这题的难点首先在读题。。。去重是对于每一个子序列分别去重，比如 1,2,4,2,2 去重之后是 1,2,4。而不是有两个子序列完全相同时去掉其中一个。

然后读完这个题之后我们发现，如果是有重复的就消去只剩一个，那么每个数在一个子序列中只会出现一次。假设在一个长度为 t 的序列中，数字 x 出现了 k 次，那么它的贡献就是 (2^t-2^{n-k})x。

这个式子的证明就是容斥，整体减不合法。如果不选数 x 的话就是剩下 t-k 个随便选，也就是 2^{t-k}。

将这个式子推出来之后我就想直接莫队了，却忽略了一个最大难点，那就是随着区间的移动，我们的区间长度是在不断改变的，也就是 t 其实是不确定的。

所以我们必须将所有贡献以一种形式存储下来，以便莫队移动区间后改变 t 之后使用。

考虑一个在 \text{Ynoi} 中常见的思路，根号分治。

当出现次数 \leq \sqrt n 次的时候，我们出现记录次数，并且记录出现这个次数的数的和。由于乘法结合律，所以我们将这些数绑在一起乘是没有问题的。

当出现次数 > \sqrt n 次的时候，我们记录数，并且直接用 cnt 数组来查看次数。

大体思路明确了，剩下几个小问题

我们的时间复杂度是 n\sqrt n 的，但是如果一不小心就会退化成 n\sqrt n\log n。

对于这个问题我们有两个东西要重点说一下。

1.维护出现次数 > \sqrt n 的数，我们发现，在这若干种数中，只有不到 \sqrt n 个数出现次数有可能 >\sqrt n。所以我们考虑先预处理一下，将所有在整个序列中出现次数 >\sqrt n 的数都处理出来。也就是说，我不管这个数实际出现几次，我只管它的“天赋”，也就是最多出现的次数会不会超过 \sqrt n。如果会的话，我就直接通过 cnt 处理。时间复杂度还是 n\sqrt n。

2.快速查询 2^t 的方法。这个方法很明显不能用快速幂，否则时间复杂度会退化。分析复杂度发现，我们可以容忍的最大复杂度是预处理 O(\sqrt n)，查询 O(1)。比起查询的 O(1)，我们发现预处理的时间较为宽裕，所以我们考虑光速幂，即预处理出来 2^0,2^1...,2^{\sqrt n-1} 以及 2^{\sqrt n},2^{2\sqrt n}...2^{\sqrt n\times \sqrt n}。然后 O(1) 组合相乘查询即可。

注意其中的 \sqrt n 均表示 n 的算术平方根下取整。

然后这题也没啥细节了，反正我是用了很短的时间一遍就过了。