自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:06:44，当前版本为作者最后更新于2023-01-27 17:17:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我想了很久都不知道 4log 怎么卡成 3log。。。

然后问了 142857，他说了一个 3log 做法。和 4log 的思路完全不相同。

对每个值维护对于其每个长度的数量。单次修改的时候把 $i$ 左右两边的前后缀 or 分段求出来，这样共有 $O(n\log^2 a)$ 个值。

然后考虑对每个值的区间长度数量修改。修改的时候，就是左边有一个区间 $[l_1,r_1]$，右边有一个区间 $[l_2,r_2]$，这个值的区间 $L\in [l_1,r_1],R\in [l_2,r_2]$。

对于一个长度 $len$，$l_1\le L\le r_1,l_2\le L+len-1\le r_2$ 即共有 $\min(r_2-len+1,r_1)-\max(l_2-len+1,l_1)+1$ 个区间。

这显然是个分段的一次函数。也就是要支持区间加一次函数，求第一个非 $0$ 的值。

这个地方有点诈骗的意味。如果你去维护区间最大值肯定没救。然而要求的是非 $0$ 的值而且所有数都非负所以维护区间和就可以了。。。

用线段树维护，单次修改之后在线段树上二分，然后就可以对每个值求出其最短区间，用平衡树维护值即可。

时间复杂度 $O(n\log n\log^2a)$。