如果WA on #3(line 23,read 5,expected 9)
查看原帖
如果WA on #3(line 23,read 5,expected 9)
544188
lkwbian楼主2024/7/2 17:35

∵\because每个节点的 lmlm , rmrm 都可能 <0<0 。

∴\therefore父节点的权值可能为最大子段和

∴\thereforepush_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);
2024/7/2 17:35
加载中...