洛谷 P5066 [Ynoi2014] 人人本着正义之名
Vanilla_chan
·
·
题解
Problem
对一个01序列进行以下m个操作：
- 区间覆盖为
0
- 区间覆盖为
1
- 将区间[l,r-1]中的数a_i同时变为a_i与a_{i+1}按位或的值
- 将区间[l+1,r]中的数a_i同时变为a_i与a_{i-1}按位或的值
- 将区间[l,r-1]中的数a_i同时变为a_i与a_{i+1}按位与的值
- 将区间[l+1,r]中的数a_i同时变为a_i与a_{i-1}按位与的值
- 查询区间和
强制在线。
## Solution
刚开始思考的时候，看到数据范围中有着**随机生成**这个部分分，想到了珂朵莉树（毕竟背景是珂朵莉嘛~）。
但是貌似珂朵莉无法对操作$3,4,5,6$进行很好的维护。
又注意到这个序列只有`01`，这里可是一个突破口！
我们手玩一下样例中的`01001`：
首先分段：
$$
[0][1][00][1]
$$
操作$3$：
$$
[11][0][11]
$$
可以发现，所有的`0`段的最右边的`0`都变成了`1`，也就是所有的`1`段的长度向左扩展了1位（如果它的左边还有的话）。
操作$4,5,6$也类似，每次一种段只会有边界上的改变。
这个貌似就很好维护了。
但是我们都知道，珂朵莉维护的是一段值相同的区间，却不一定随时都是**极长**的。
即，我们需要让一个`0`段的左右保证是`1`段（或者没有）。
我们手写一个平衡树（而不用`set`）来维护这些子段。因为左/右端点移动量显然是可以叠加的，可以在平衡树上打标记维护。
但是有两个问题：**如何保证每个子段都是极长的？如何保证没有空的子段？**
如果子段不是极长的，那么就会有相邻的同值子段，其中一个移动边界时会占领另一个，但是显然不需要移动。对于这个问题比较简单，只要在区间赋值的时候多向两遍拓展即可。其他的操作都是不会造成这种非极长子段的。
当我们在移动边界的时候，会出现一个子段的长度已经变成了0的情况，会导致总段数剧增，无法保证时间复杂度。
在平衡树上再维护两个值：子树中最短的`0/1`段长度即可。
发现有长度为0的段时直接暴力删除。
平衡树的一个节点维护了：左端点，右端点，子段的值，子树和，子树中`0`段的数量，子树中`1`段的数量，子树内最短的`0`段，子树内最短的`1`段，`lazy`标记。
然后这道题就结束了。
## Code
按照传统（？），只给部分代码供参考。有问题也可以私信(如果我还没AFO的话)
[剪切板](https://www.luogu.com.cn/paste/mr5x0v35)
## Other
唉，2021年了，这道题需要一点卡常了……
原本$Ynoi$是很友好的，但是有些人用错误的时间复杂度乱搞过去了，所以只能加强加强再加强，导致正解想要过去也比较困难了……
[$\textbf{2021-03-31 08:00:25 thus,AC.}$](https://www.luogu.com.cn/record/48728244)
附上[debug日志](https://www.luogu.com.cn/blog/Vanilla-chan/luo-gu-p5066-ynoi2014-ren-ren-ben-zhuo-zheng-yi-zhi-ming-debug-log)。祝您早日AC。