题解：AT_arc130_e [ARC130E] Increasing Minimum

TTpandaS · 2025-09-15 14:33:50 · 题解

考虑假设答案最初全部为 1，然后为其打补丁使得通过这些限制。

对于第 k 个限制 i_k，要保证 a_{i_k} 是当前最小值，那么全局与 a_{i_k} 取 \max，然后再将 a_{i_k} 加一。实现单点查询，全局取 \max，单点加一。

然后以打完补丁的数组模拟操作，如果此时 a_{i_k} 不是最小值那么就是无解。实现单点加一，全局查询最小值。

这样可以通过 97 个点（共 99 个点）。发现打补丁的次数越多正确性越高，于是以第一次打完补丁的数组当作初始答案，再打一次补丁即可通过此题。