「KDOI-03」还原数据 题解
Error_Yuan · · 题解
T1 题解(定位:签到题):
-
由于
\max 操作的贡献无法被后面的\max 操作抵消,倒序考虑操作,以a' 为初始数组,1 操作加法变减法,对于2 操作,合法的x 一定要满足,x\le 区间[l,r] 中的最小值,否则区间[l,r] 中的最小值经过正序操作后会大于最终值。 -
而
x 可以直接取等号,原因是要使得尽可能多的值达到最终值。 -
由于保证有解,不需要进行额外判断。
-
建议手动模拟一下过程。
-
最终,写一颗支持区间加区间查询最小值的线段树即可。
-
鲜花:本题本来有判断是否有解,数据给了 不可以,总司令 40。