rt,以下是本人第一版代码的一部分。
其中有两处显然的错误,分别是pushup函数中大于号写成小于号,以及addtag函数中更新sum时直接用lazytag1更新。
然而,这份代码在你谷数据下得到了80pts的高分(TLE on #9 & #10), #9本地测试的结果也无误。
值得注意的是,以上两点错误任意修正一处都会WA一大片
负负得正了属于是
inline void pushup(ll rt)
{
tr[rt].sum=tr[ls].sum+tr[rs].sum;
tr[rt].mxa=max(tr[ls].mxa,tr[rs].mxa);
tr[rt].mxb=max(tr[ls].mxb,tr[rs].mxb);
if(tr[ls].mxa==tr[rs].mxa)
{
tr[rt].sec=max(tr[ls].sec,tr[rs].sec);
tr[rt].cnt=tr[ls].cnt+tr[rs].cnt;
}
else if(tr[ls].mxa<tr[rs].mxa)
{
tr[rt].sec=max(tr[ls].sec,tr[rs].mxa);
tr[rt].cnt=tr[ls].cnt;
}
else if(tr[ls].mxa>tr[rs].mxa)
{
tr[rt].sec=max(tr[rs].sec,tr[ls].mxa);
tr[rt].cnt=tr[rs].cnt;
}
}
inline void addtag(ll rt,ll l1,ll l2,ll l3,ll l4)
{
tr[rt].sum+=(R-L+1)*l1;
tr[rt].mxb=max(tr[rt].mxb,tr[rt].mxa+l3);
tr[rt].mxa+=l1;
if(tr[rt].sec!=-INF)tr[rt].sec+=l2;
tr[rt].l3=max(tr[rt].l3,tr[rt].l1+l3);
tr[rt].l4=max(tr[rt].l4,tr[rt].l2+l4);
tr[rt].l1+=l1,tr[rt].l2+=l2;
}