第十分块 题解

· · 题解

去年写的东西现在啥都不会了

第十分块。

这题是个操作分块套序列分块。正解复杂度为 O(n\sqrt n)（n 与 m 同阶），所以分析时块大小默认为 \sqrt n。实际取值时要考虑常数因子的影响。

操作分块，即把每 \sqrt n 次操作一起处理。这些操作中，有 O(\sqrt n) 次修改和 O(\sqrt n) 次查询。

对询问，按照 x 从小到大排序。维护一个 01 序列表示每个位置是否小于等于 x。每次把新的符合条件的位置改成 1。不考虑排序，这里总复杂度 O(n)。

对于那些修改操作，一个显然的套路就是插入后按顺序撤销。

我们需要设计这样一个数据结构，支持 O(1) 把一个位置的 0 变成 1，O(\sqrt n) 查询一段区间的极长连续 1 区间长度的平方和（与平方有关的信息）。还要支持 O(1) 按顺序撤销。

序列分块。考虑对每个极长连续 1 区间，在开头处记录其结尾位置，在结尾记录其开头位置。则新插入一个 0 的时候，可以 O(1) 将这个点的左右（如果存在）进行合并。再用一个数组记录一下各个块的答案即可。

对于撤销操作，由于每次插入只影响了两个点的值，所以记录下原来的值及其位置，询问结束后暴力还原即可。

查询的时候，我们记录当前极长连续 1 区间的左端点，边角扫描，对于整块，可以直接通过维护的值来得出这个块的前缀 1 区间长度和后缀 1 区间长度。将其前缀与之前的左端点计算贡献，新的左端点即为后缀的那个点。然后中间的部分，通过记录的块内答案减去两边要和其他块计算答案的部分的贡献即可。

这样就做到了每块操作 O(n) 处理，则总时间复杂度 O(n\sqrt n)。

记得卡卡常。