由于吉司机线段树的时间复杂度基于势能分析,所以 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));
这样做可能由于两子树最大值相同而导致错误,正确写法应该进行逐一判断:
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。