题解 P5066 【[Ynoi2014]人人本着正义之名】

Sol1 · 2020-04-06 22:25:35 · 题解

Update：感谢 _Guoyh_ 神仙的提醒，来更题解了。

Problem：

给定一个序列 a_{[1,n]}，支持区间赋值、区间每一个数同时与/或上旁边的数，和区间求和。序列长度、操作次数都是 3\times 10^6 级别。

Solution：

这个东西看上去显然是十分不可做的。。。

于是看了一遍番，发现你还是不会做

所以我们先考虑 80 分的做法，即数据随机。

数据随机+区间赋值，显然的珂朵莉树。

于是直接珂朵莉树暴力维护就可以拿到 80 分。

我们从这个解法中挖掘到一个性质：每次区间与/或上相邻的数相当于极长连续同色子段的扩散与收缩。

比如 3 操作，如果原子段是这样的：

提取出极长连续子段：

然后对整个区间执行 3 操作后：

发现，这个操作其实就是 0 的极长连续段向左收缩 1 单位长度，1 的极长连续段向左扩散 1 单位长度！

手模一下，可以发现 4~6 的操作都有这个性质！

然后我们就可以手写一个平衡树来维护这些子段，因为这个操作等价于左端点 l 移动一定长度 \Delta l，r 移动一定长度 \Delta r，而这两个量显然是可以叠加的，所以就可以打标记维护了。

具体来说，每一个子段存储：该节点对应的左右端点、子段的值、子树对应的区间的和，子树内 0 段/1 段的数量（用来在处理标记时快速更新）、子树内 0 段的最小长度、 1 段的最小长度（后面说这个的用处）、标记。

为了方便起见维护了一下子树的 size，但是其实可以计算得到。

但是我们注意到两点：1. 如果有两个连续的同色子段，会同时扩散/收缩，但显然其中一个不应该扩散/收缩；2. 有可能产生长度为 0 的子段，此时无法在打标记之后快速更新区间和。

第一个问题没有什么比较好的解决方法，必须保证子段极长。具体来说，我们不去将一个极长段拆成两个。

如何做到这一点呢？我们首先考虑 1 和 2 操作：

这里以 2 操作为例，思想大致就是覆盖之后把两端同色的归并进去。放个图大致说明一下过程。

那么 3,4,5,6 操作呢？

以 3 操作为例说明一下过程。

对于 7 操作，可以类似上述操作提取出区间后减掉两边的零散部分。因为比较好想就不再赘述。

于是我们只要在一开始按照极长子段建好树就可以保证这些子段一直是极长的了~

那么第 2 个问题怎么解决？

定义势能 E 为这棵平衡树内的节点数量，我们发现，上述操作每一次对 E 的增加是 O(1) 的，最坏情况是在一个极长段内插入一个颜色相反的极长段，会导致势能 +2。

所以这棵树的最大势能是 O(n+m) 级别的。

我们考虑暴力删去这些 0 长度的点，并将两侧的点归并为一个。

这样最坏情况下是删去了边界上的点，势能 -1。

相当于使用 O(\log n) 的复杂度减小 O(1) 势能。

显然你只有 O(n+m) 的势能可以减小，所以均摊一下这个复杂度就是 O((m+n)\log n)，可以接受。

前面说要维护最小长度，目的就是 O(\log n) 找到一个 0 长度点删去。

对 0 和 1 分别维护的意义在于打标记的时候可以快速更新。

使用 FHQ-Treap 实现，这道题就做完了~

时间 O((m+n)\log n)，空间 O(n)。

注意这题我强烈建议不要用 splay，常数会很大，而且因为不支持 split 会导致很难写。

这个写法空间常数略大，有两种解决方法：一，二分取一个值，我取的是 4.2\times 10^6 过掉的。

二，写一个垃圾回收，这样空间可以直接取 3\times 10^6。但是要处理更多细节。

最终 6.43s/302.95MB 通过本题。

平衡树部分的代码，供参考

Credit:

感谢 noip 在春令营课上讲解大致做法。

感谢 万万没想到 的 FHQ-Treap 学习笔记和解法。

最后留下纪念：

公元 2020 年 4 月 6 日，北京时间 20 点 13 分 21 秒，洛谷用户 ClCN 在经过 20 小时的奋战之后，成功 AC P5066 [Ynoi2014]人人本着正义之名。

以此纪念。