社区讨论
对于tj的理解
P6242【模板】线段树 3(区间最值操作、区间历史最值)参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mjp71i6c
- 此快照首次捕获于
- 2025/12/28 11:52 2 个月前
- 此快照最后确认于
- 2025/12/31 20:40 2 个月前
为什么要将区间最值转化为最值的区间加我有一个理解(可能对于别人来讲有点显然)
区间最值经过我们的转化之后只对当前的最值有效,也就是最值的区间加,可是为什么大多数题解都进行了这个转化呢?不进行转化能不能做呢?(不要嘲笑我我真的想这个+尝试不进行转化写代码了俩小时)(因为我最假女选手那题我就知道可以转化但是还是没转化写的)
这里有一种理解:
我们先将区间最值转化为当前最值的区间加来理解,也就是当前非最值和当前最值的加法的操作序列是不一样的,我们要求历史最大值相当于在操作序列里找到前缀最大值,而两个不一样的操作序列前缀最大值的位置可能也不一样,因此如果只开4个lazytag是记录不了真实加/max,最值的区间历史最值加/max,非最值的区间历史最值加/max的,而区间最值转化相当于将最值的区间历史最值加/max的俩个融合成一个lazytag,将非最值的区间历史最值加/max的的俩个融合成一个lazytag,所以不转化理论上我没写是可以做的,只不过要多开2个lazytag
回复
共 0 条回复,欢迎继续交流。
正在加载回复...