Hi guys! Please help me to understand this code!

Revision en2, by Friren, 2024-03-19 06:50:30

In this problem for 100 pts needed to use centroid or hld, but I found the one submussion that solved it just with segment tree, which make curious, but merge function I still cannot understand it. Can someone explain it to me, I am trying to upsolve it for 3 days straight.

seg[ind].pref=max(seg[2*ind+1].pref, seg[2*ind+1].sum+seg[2*ind+2].pref);

seg[ind].suff=max(seg[2*ind+2].suff, -seg[2*ind+2].sum+seg[2*ind+1].suff);

seg[ind].sum=seg[2*ind+1].sum+seg[2*ind+2].sum;

seg[ind].allans=max(seg[2*ind+1].allans+seg[2*ind+2].sum, -seg[2*ind+1].sum+seg[2*ind+2].allans);

seg[ind].prefans=max({seg[2*ind+1].prefans, seg[2*ind+1].allans+seg[2*ind+2].pref, -seg[2*ind+1].sum+seg[2*ind+2].prefans});

seg[ind].suffans=max({seg[2*ind+2].suffans, seg[2*ind+2].allans+seg[2*ind+1].suff, seg[2*ind+2].sum+seg[2*ind+1].suffans});

seg[ind].ans=max({seg[2*ind+1].ans, seg[2*ind+2].ans, seg[2*ind+1].suffans+seg[2*ind+2].pref, seg[2*ind+1].suff+seg[2*ind+2].prefans});

I didnt get allans,prefans,suffans, their value, what their values represent? Hope for your help!

P.S downvotes are welcome, I know this is again stupid blog of beggin help from newbies.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Friren 2024-03-19 06:50:30 98
en1 English Friren 2024-03-19 06:46:41 1222 Initial revision (published)