∵每个节点的 lm , rm 都可能 <0 。
∴父节点的权值可能为最大子段和
∴push_up时
从
if(!k)return;
c[k].siz=c[lss].siz+c[rss].siz+1;
c[k].lm=max(c[lss].lm,c[lss].sum+max(c[k].x,c[k].x+c[rss].lm));
c[k].rm=max(c[rss].rm,c[rss].sum+max(c[k].x,c[k].x+c[lss].rm));
c[k].ans=max(max(c[lss].ans,c[rss].ans),max(c[lss].rm+c[k].x,c[rss].lm+c[k].x));
c[k].ans=max(c[k].ans,c[lss].rm+c[k].x+c[rss].lm);
c[k].sum=c[lss].sum+c[rss].sum+c[k].x;
添一句
c[k].ans=max(c[k].ans,c[k].x);