Solution P11982 | while seeing orderly streetlights

BreakPlus · 2025-10-17 08:28:34 · 题解

思路借鉴了 @Daniel_lele，这里给出一些具体实现细节。

考虑根号重构，每次把接下来 \sqrt{n} 次要修改的位置拿出来，令其下标序列为 [p_1,p_2,\cdots,p_k]。

Part 1

先计算至少有一个路灯在 p 中的二元组。构建一个新的序列如下：

其中 f(p_i,p_{i+1}) 表示在 p_i 和 p_{i+1}（均不含）之间的最高的路灯。所有 f 在这个块内均不会被修改，但是 p_i 的高度会被修改。

• 计算两个路灯都在 p 中的二元组

  把上述序列抠出来，跑单调栈，对每个路灯找到第一个高度 \ge 它的前驱，判断高度是否相等且二者均在 p 中即可。

• 计算只有一个路灯在 p 中的二元组

  每个 p 中的路灯最多只能和一个前驱、一个后继产生贡献（也就是这类贡献最多只有 \mathcal{O}(\sqrt{n}) 个）每次修改一个路灯的时候，对这个路灯用线段树上二分，重新找其在整个序列中的前驱后继。

  但是修改一个 p_i 的高度可能会导致跨过它的二元组也失效/复活。可以在查询的时候利用之前的单调栈维护的信息，\mathcal{O}(\sqrt{n}) 暴力重新检查当前所有这类二元组是否合法。

Part 2

然后考虑两个路灯都不在 p 中的贡献。先直接在原序列中去掉被修改过的路灯，剩下的可以 \mathcal{O}(n) 单调栈跑出所有合法二元组，给它们编号，并用编号建立出它们的树形关系。

修改一个 p_i 的高度时会破坏一些原有的二元组。找到跨过 p_i 的两端点距离最近的二元组编号 low_i，那么从它开始往上的一条链会被标记为不再合法。

这可以用树剖+线段树维护。具体地，给树上所有点一个标记值 w_i，每次把一条链上的 w_i 加 \pm 1（加入或撤销），并查询全局 0 的个数（即没有被标记过的点树），这通过维护区间最小值及其个数就能做到。

还有一个问题是怎么找 low_i。这里提供一个算法：维护一个序列 d，对于每个二元组 [l,r]，让 d_l 加 1，让 d_{r-1} 减 1。求 low_i 的时候相当于找到一个最小的 x 使 \sum \limits_{k=x}^{p_i-1} d_k >0。于是把 d 求个前缀和后跑单调栈就可以线性预处理 low_i。

现在来看看复杂度。重构的时候，线段树、树剖、单调栈，这些预处理全都是线性的；每次查询会把 \sqrt{n} 个点拿出来再跑单调栈；一些 \text{polylog} 的东西忽略不计（实际上运行起来不能忽略不计），复杂度 \mathcal{O}(n\sqrt{n})。

目前只在 loj 过了 /kel

听耳边熙熙攘攘的声音如风

辨别不出你方位是我的瞳孔

当看见一排工整有序的路灯

低着头苏醒了