社区讨论
警示后人
P6242【模板】线段树 3（区间最值操作、区间历史最值）参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lzmd6hz7
- 此快照首次捕获于
- 2024/08/09 15:07 2 年前
- 此快照最后确认于
- 2024/08/09 15:47 2 年前
由于吉司机线段树的时间复杂度基于势能分析，所以
update_min 函数的错误可能引起 #9 #10 的 TLE，从而得到 80pts 的分数。本人的错误在于对严格次大值的更新，错误：
CPPs[x].maxse=max(min(s[x<<1].maxx,s[x<<1|1].maxx),max(s[x<<1].maxse,s[x<<1|1].maxse));//maxx 为最大值，maxse为次大值
这样做可能由于两子树最大值相同而导致错误，正确写法应该进行逐一判断：
CPPif(s[x<<1].maxx<s[x<<1|1].maxx) s[x].maxse=s[x<<1].maxx;
else if(s[x<<1].maxx>s[x<<1|1].maxx) s[x].maxse=s[x<<1|1].maxx;
else s[x].maxse=max(s[x<<1].maxse,s[x<<1|1].maxse);
80->100。
回复
共 2 条回复，欢迎继续交流。
正在加载回复...