警示后人
查看原帖
警示后人
310639
yingkeqian9217楼主2024/8/9 15:05

由于吉司机线段树的时间复杂度基于势能分析,所以 update_min 函数的错误可能引起 #9 #10 的 TLE,从而得到 80pts 的分数。

本人的错误在于对严格次大值的更新,错误:

s[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为次大值

这样做可能由于两子树最大值相同而导致错误,正确写法应该进行逐一判断:

if(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。

2024/8/9 15:05
加载中...