题解：AT_abc428_f [ABC428F] Pyramid Alignment

· · 题解

考虑两种操作，左端点要么是变成一个数，要么是变成一个数剪掉长度。

所以考虑设左端点都为 a + b \cdot len，其中 len 为线段长度。

然后我们把 a, b 相同的分为一类，然后每一类对应一个区间。

那么每次修改就把在 1 \sim v 中的区间和 v + 1 \sim n 的区间分裂开，然后将在 1 \sim v 的区间都删除，并修改成对应的 a + b \cdot len。

然后显然左右端点都有单调性，直接二分即可找出合法区间。