专栏文章

Solution P11982 | while seeing orderly streetlights

BBreakPlus
P11982题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minl68z4
此快照首次捕获于
2025/12/02 04:12
3 个月前
此快照最后确认于
2025/12/02 04:12
3 个月前
查看原文
思路借鉴了 @Daniel_lele，这里给出一些具体实现细节。
考虑根号重构，每次把接下来 n\sqrt{n} 次要修改的位置拿出来，令其下标序列为 [p1,p2,⋯ ,pk][p_1,p_2,\cdots,p_k]。

Part 1

先计算至少有一个路灯在 pp 中的二元组。构建一个新的序列如下：
[p1,f(p1,p2),p2,f(p2,p3),⋯ ,f(pk−1,pk),pk][p_1,f(p_1,p_2),p_2,f(p_2,p_3),\cdots,f(p_{k-1},p_k),p_k]
其中 f(pi,pi+1)f(p_i,p_{i+1}) 表示在 pip_i 和 pi+1p_{i+1}（均不含）之间的最高的路灯。所有 ff 在这个块内均不会被修改，但是 pip_i 的高度会被修改。
  • 计算两个路灯都在 pp 中的二元组
    把上述序列抠出来，跑单调栈，对每个路灯找到第一个高度 ≥\ge 它的前驱，判断高度是否相等且二者均在 pp 中即可。
  • 计算只有一个路灯在 pp 中的二元组
    每个 pp 中的路灯最多只能和一个前驱、一个后继产生贡献（也就是这类贡献最多只有 O(n)\mathcal{O}(\sqrt{n}) 个）每次修改一个路灯的时候，对这个路灯用线段树上二分，重新找其在整个序列中的前驱后继。
    但是修改一个 pip_i 的高度可能会导致跨过它的二元组也失效/复活。可以在查询的时候利用之前的单调栈维护的信息，O(n)\mathcal{O}(\sqrt{n}) 暴力重新检查当前所有这类二元组是否合法。

Part 2

然后考虑两个路灯都不在 pp 中的贡献。先直接在原序列中去掉被修改过的路灯，剩下的可以 O(n)\mathcal{O}(n) 单调栈跑出所有合法二元组，给它们编号，并用编号建立出它们的树形关系。
修改一个 pip_i 的高度时会破坏一些原有的二元组。找到跨过 pip_i 的两端点距离最近的二元组编号 lowilow_i，那么从它开始往上的一条链会被标记为不再合法。
这可以用树剖+线段树维护。具体地，给树上所有点一个标记值 wiw_i，每次把一条链上的 wiw_i 加 ±1\pm 1（加入或撤销），并查询全局 00 的个数（即没有被标记过的点树），这通过维护区间最小值及其个数就能做到。
还有一个问题是怎么找 lowilow_i。这里提供一个算法：维护一个序列 dd，对于每个二元组 [l,r][l,r]，让 dld_l 加 11，让 dr−1d_{r-1} 减 11。求 lowilow_i 的时候相当于找到一个最小的 xx 使 ∑k=xpi−1dk>0\sum \limits_{k=x}^{p_i-1} d_k >0。于是把 dd 求个前缀和后跑单调栈就可以线性预处理 lowilow_i。
现在来看看复杂度。重构的时候，线段树、树剖、单调栈，这些预处理全都是线性的；每次查询会把 n\sqrt{n} 个点拿出来再跑单调栈；一些 polylog\text{polylog} 的东西忽略不计（实际上运行起来不能忽略不计），复杂度 O(nn)\mathcal{O}(n\sqrt{n})。
目前只在 loj 过了 /kel
听耳边熙熙攘攘的声音如风
辨别不出你方位是我的瞳孔
当看见一排工整有序的路灯
低着头苏醒了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...