题解 P6019 【[Ynoi2010]D1T2】

mrsrz · 2020-01-31 23:31:37 · 题解

本来不想发题解的，lxl 让我发那我也就分享一下我的大常数维护方法了。

赛时就写了一部分，赛后又补充了没想到的部分，可能有点不太详细

不懂的地方可以私信问我，但是最好不要想着去哪个地方找我的代码交上去，过不了不要怪我

序列分块。

分块，维护每种数的前缀出现次数，以及每种数的前缀出现次数的平方。

我们需要计算一段区间的每种数的出现次数的平方的和，考虑记录前缀的平方和，使用 (a-b)^2=a^2-2ab+b^2 计算。

维护 f(i,j) 表示 \sum_x cnt(x,i)\cdot cnt(x,j)。其中 cnt(x,k) 表示颜色 x 在前 k 个块中的出现次数。

对 f(i,j) 的修改，考虑块 k 处的修改，设这种颜色在前 i 块和前 j 块中的出现次数为 a,b，在 块 k 中的出现次数增加了 x。

对于 i\leq k,k\leq j 的，他们的变化为 a(b+x)-ab=ax。我们对每个左端点为 i 的 f(i,\texttt*) 都记录变化量。

对于 i<k,j<k 的，变化为 0。

对于 k<i,k\leq j 的，变化为 (a+x)(b+x)-ab=ax+bx+x^2。我们对每个左端点为 i 的 f(i,\texttt*) 都记录变化量 ax，对每个右端点为 i 的 f(\texttt*,i) 都记录变化量 bx+x^2。

这部分可以使用差分的技巧做到 O(1) 修改 O(\sqrt n) 查询。

那么块 i 与 j 之间的所有数的出现次数的平方和，我们只需要知道前 i 个块的平方和，前 j 个块的平方和，f(i,j) 的值，就可以求得。计算的复杂度为 O(\sqrt n)。

关于修改操作，边角暴力，中间的如果只有一个数则 O(1) 修改，这会给这个块产生 O(1) 个额外颜色段，否则 O(\sqrt n) 删除块中的段贡献，总产生的颜色数为 O(n+m)。此时更新 f 的复杂度为 O((n+m)\sqrt n)。

然后对于一个块，如果只有一种颜色，我们不把他计算到 f 中而是在查询的时候计算这个块的贡献。

那么需要计算进 f 的颜色段个数是 O(n+m)，所以每次对颜色段进行重新计算前缀信息，时间复杂度 O((n+m)\sqrt n)。

总时间复杂度 O((n+m)\sqrt n)，空间复杂度 O(n \sqrt n)。