序列分块，链表以及值域均摊

· · 题解

Part1 问题引入

给定序列 a_i，要求区间不等于 x 的数减去 x，或区间求和，n,m\le5\times10^5。

发现这个东西用线段树等数据结构无法维护，自然就要往分块方面想。

这题的思路是很自然的，没有需要构造的地方，让人感觉每一步的思考都很合理。

Part2 非暴力不可过解

对于一个操作 1，考虑 a_i 的变化：

如果某一时刻 a_i<0，则对于之后的每一个操作（区间包含 i） a_i 都会减少 x，对于这些 a_i，我们可以整体打标记。

所以我们可以对序列分块，块内只维护大于 0 的数值，而每一个 a_i 会在第一次的 a_i<x 时删除。

而 a_i>x 也是很多的，我们也可以打整体标记（和之前共用一个标记），于是每次我们只要对于 a_i=x，让 a_i\leftarrow a_i+x 就可以了，这部分要求将同一个值的数字一起维护，所以需要使用链表将值相同的连到一起来。

于是我们每一次操作需要不停地找最小值，如果当前最小值 v<x，则弹出，v>x 直接退出，否则 v=x，就 v\leftarrow2v，同时让块的 sum\leftarrow sum+x\times sz_v，即有 sz_v 个数字不会变化，这部分可以用堆维护。

重构块时要将所有同数值链表全部拆散，重新排序建堆。

于是时间复杂度稳稳地落在了 O(m\sqrt n\log_2n)，显然不能通过。

当然你可以用压位 Trie 和哈希表维护，这样时间变成了 O(m\sqrt n\log_wV)，但由于需要动态开点，所以空间是 O(n\log_wV) 的。

Part3 值域均摊优化

想到上面的做法我就不会优化了，甚至一再认为自己的想法有误，然而离通过只差一个优化。

考虑每一次的 v\leftarrow2v，即更改最小值是复杂度瓶颈，我们需要想办法快速地调整最小值。

发现调整最小值就是在 v\leftarrow2v 后跳过比自己小的数到后面去，v' 会被 v 跳过当且仅当 v'\in(v,2v)，但是在这次操作实际意义上 v'\leftarrow v'-v<\dfrac v 2，而一个数字最多会有 \log_2V 次除以 2，所以暴力跳过的均摊时间为 O(n\log_2V)。

这里有一个细节就是如果存在相等的，即 v'=2v，则必须将两者合并而非简单接在后面，因为只有保证块内同数值的链表只有一个才能在 O(1) 的时间内移动最小值（即最小值不能有多个）。

然后我在这里用了 vector::insert 就炸了，必须要一直 pop_back 并存起来，再 push_back 回去，你也可以手写链表，但千万不要用 std::list，这个实在是太慢了！

Part4 散块重构

论如何 O(\sqrt n) 重构散块？

首先遍历同数值的链表，将每一个数字（除去整体标记的部分）更新，然后修改区间 [l,r]。

发现这时我们并不能暴力 sort，需要在遍历链表时，将需要减 x（a_i>x\land i\in[l,r]）的数放在一边，其他的放在另一边修改之后归并就行了。

Part5 其他做法

首先分块做法时间复杂度 O(m\sqrt n+n\log_2V)，空间 O(n)。

一个常见的做法是倍增分块，O((n+m)\log n\log V)，不过没有利用到本题小于 x 数字暴力减的性质。

所以最优秀的方法还是记录次小值，和线段树 3 类似，时间复杂度 O(n\log n\log V+m\log n)，常数极小。