这就是 142857 的实力 | 题解 P5065 [Ynoi2014] 不归之人与望眼欲穿的人们

· · 题解

我想了很久都不知道 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)。