P4513 or GSS1 or GSS3
问一下这种做法对不对。
线段树的每个结点维护区间边界 [l,r],最大子段和 sum,在最大子段左侧的区间和 s1,在最大子段右侧的区间和 s2(即 s1+sum+s2=[l,r] 区间和)。
在 update/pushup 时,取得 s1,A,s2,s3,B,s4 六个值,分别对应左孩子和右孩子的 s1,sum,s2(有点重名了抱歉)。 然后分情况计算出结点 k 的 s1,sum,s2。

这部分的代码:
LaCampanella ans; // 自定义结构体
ans.l=L.l,ans.r=R.r;
ans.sum=-inf;
int A=L.sum,
B=R.sum,
s1=L.s1,
s2=L.s2,
s3=R.s1,
s4=R.s2;
if(A>ans.sum)
{
ans.sum=A;
ans.s1=s1,ans.s2=s2+s3+B+s4;
}
if(B>ans.sum)
{
ans.sum=B;
ans.s1=s1+A+s2+s3,ans.s2=s4;
}
if(A+s2+s3+B>ans.sum)
{
ans.sum=A+s2+s3+B;
ans.s1=s1,ans.s2=s4;
}
if(A+s2+s3>ans.sum)
{
ans.sum=A+s2+s3;
ans.s1=s1,ans.s2=B+s4;
}
if(s2+s3+B>ans.sum)
{
ans.sum=s2+s3+B;
ans.s1=s1+A,ans.s2=s4;
}
if(A+s2+s3+B+s4>ans.sum)
{
ans.sum=A+s2+s3+B+s4;
ans.s1=s1,ans.s2=0;
}
if(s1+A+s2+s3+B>ans.sum)
{
ans.sum=s1+A+s2+s3+B;
ans.s1=0,ans.s2=s4;
}
return ans;
然后现在只有 9 分。问一下这个做法是否正确,或者是我写挂了/kk
完整代码。
QAQ