「KDOI-03」还原数据 题解

Error_Yuan · 2022-11-13 22:05:48 · 题解

T1 题解（定位：签到题）：

• 由于 \max 操作的贡献无法被后面的 \max 操作抵消，倒序考虑操作，以 a' 为初始数组，1 操作加法变减法，对于 2 操作，合法的 x 一定要满足，x\le 区间 [l,r] 中的最小值，否则区间 [l,r] 中的最小值经过正序操作后会大于最终值。

• 而 x 可以直接取等号，原因是要使得尽可能多的值达到最终值。

• 由于保证有解，不需要进行额外判断。

• 建议手动模拟一下过程。

• 最终，写一颗支持区间加区间查询最小值的线段树即可。

• 鲜花：本题本来有判断是否有解，数据给了 不可以，总司令 40。