专栏文章

CF1904D2 Set To Max (Hard Version)

2025/09/04 20:41CF1904D2题解参与者 1已保存评论 0

文章操作

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

当前评论: 0 条
当前快照: 1 份
快照标识符: @mio0j21m
此快照首次捕获于: 2025/12/02 11:22
此快照最后确认于: 2025/12/02 11:22

对于每个

a_i \neq b_i

，显然

a_i > b_i

无解。

二分找到左右离

b_i

最近的

a_j

。若

i \sim j

之间存在一个

k

满足以下两个条件则不合法：

$a_k > b_i$ ，此时无法将 $a_i$ 覆盖为 $b_i$ ，而是更大的 $a_k$ 。
$b_k < b_i$ ，此时操作后一定会有 $a_k > b_k$ ，显然不合法。

若离

b_i

两端的最近的

a_j

都不合法的话，那么这个序列无解。

用线段树等数据结构维护。

评论

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

正在加载评论...