[数据结构与算法]题解 [COCI2010-2011#7] UPIT

题解做法：块状链表。

若只有 1、2、4 操作，即题目 P1438 无聊的数列，可以用线段树 + 差分轻松维护，也可以用分块实现，这两种做法都是在线的。

新增一个 3 操作，用线段树难以在线实现插入操作，只能离线实现。如果强制在线呢？我们考虑用分块来实现。

操作 1：区间赋值。

散块暴力修改，整块用一个数组 change 记改成了啥。由于是赋值，我们将其他整块上的相关信息清空，如区间加的标记等，并且更新区间和 sum[i]=siz[i]*c。注意在每次散块赋值前，要类似线段树的 pushdown，将标记下放，即把散块所有元素的值通过标记更新。

操作 2：区间加等差数列。

这个等差数列比较特别，它的首项等于公差。如果有个整块一直是进行操作 1 和 2 的，那么整块中的相邻两个元素差是固定的，即最后一次操作 1 后的所有操作 2 对应的公差之和。因此，我们记下公差之和，以及整块中第一个元素值的增量。

操作 3：单点插入。

找到插入点对应的块，如果插入点等于当前序列长度 +1，则归为最后一块。类似暴力，将插入点后所有元素全部后移，然后填上插入的元素。用 vector 可以实现，但常数较大。正因这一部分，我使用了块状链表。

注意插入点后所有元素全部后移只能在该块内实现，若全部更新复杂度无法接受。因此我们对链表上每个元素记录它的原编号（即按输入以及插入顺序），并记录它在当前块中的排名（从前往后数第几个），在进行操作时直接遍历当前块对应链表，将符合修改目的的元素进行修改即可。

考虑极端情况：几乎所有插入全部插入在同一点，那么单块最长可达 $\text{block}+m$。若所有查询都是求序列元素总和，则统计上述情况块时的复杂度不再为 $O(\text{block})$，而是达到了 $O(\text{block}+m)$。上述两种极端操作均匀出现，忽略常数，则总复杂度最高可达 $O((\text{block}+m{)}^2)$，无法承受。因此当存在一个整块大小超过 $2\times \text{block}$ 时，我们需要重构，那么最多重构 $m/\text{block}$ 次。

注意：插入前需要下传标记，插入后若重构，需要重新统计每块大小。

操作 4：区间求和。

这个操作就非常 naive 了，仍需注意的是统计前下传标记。

认为 $n$ 和 $m$ 同阶，取 $\text{block}=\sqrt{n+m}$ 左右时，总时间复杂度约为 $O(n\sqrt{n})$。

如果您通过上述文字尚无法理解或不清楚如何实现，可以点击下面链接具体了解。

具体代码实现及全解释

其中展示的代码使用语言 C++14 提交，可以在不开启 O2 优化的情况下通过。