CF1904D2 Set To Max (Hard Version)

Autream · 2025-09-04 20:41:13 · 题解

对于每个 a_i \neq b_i，显然 a_i > b_i 无解。

二分找到左右离 b_i 最近的 a_j。若 i \sim j 之间存在一个 k 满足以下两个条件则不合法：

若离 b_i 两端的最近的 a_j 都不合法的话，那么这个序列无解。

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