WC 2023 楼梯。

Cocoly1990 · 2023-02-14 19:04:31 · 个人记录

考虑楼梯并不好刻画，考虑刻画其轮廓线，记右边界为 1，下边界为 0。记轮廓线数组为 c。

事实上，如果我们记录每个 1 之间的 0，那么得到的数组即为楼梯高度的差分数组。

然后，这个差分数组，和原楼梯显然是双射，所以这么刻画是充要的。

这么刻画的好处就是，子楼梯刚好对应轮廓线数组中的一段区间。

怎么通过一段区间还原出对应的格子是容易的，同样的，+，- 的操作也是容易的。

当然了，一段区间所代表的边界格也是好表示的，就是 \sum \limits_{i=l}^r a_i+r-l。

注意到，当且仅当我们选择的区间的两端分别是 1,0 才是合法的。

考虑询问，我们将轮廓线数组每 q 段分一段（c_1,c_{q+1},\dots,c_{n-q},c_n），那么只要存在两相邻段的首位分别是 0,1，那么这段区间就是合法的。

其实注意到，c_0=1,c_n=0（边界格数为 n-1），所以一定是有解的，考虑怎么找到这组解。

然后注意到这是一个可二分的结构，具体的：

考察一次二分点 x，如果 c_{x\times q+1}=0，那就往右边递归，否则往左。

然后，回退，可持久化即可，我也不知道出题人为啥要这么搞。

时间复杂度 \mathcal{O}(n\log ^2 V)。