I understand that we are only concerned with the points mentioned, and not all the points between 1 and 10^9. After forming a segment tree and making all the updates, how can we find the longest white colored segment?

Thank you.

It can be solved with heap by sequentially walking on control points to add/remove active segments and tracking the latest one as of input order

As for segment tree, I'd track these values

iv: longest white streak on the interval
lv: longest white streak at the begging of the interval
rv: longest white streak at the end of the interval
sv: length of segment

initially iv=lv=rv=s

now

iv = max(iv1, iv2, rv1+lv2)
lv = lv1==s1 ? s1+lv2 : lv1
rv = rv2==s2 ? rv1+s2 : rv2

But it will require lazy propagation similar to 1890 problem during painting which is quite cumbersome. The good side - it would allow "online" algorithm to give answer at every step as paiting proceeds (could be a good upgrade of a problem :)

As for this one - a simpler lazy propagation with states "0" nothing "w" completely white, "b" completely black. Upon final convergion you repeatedly forward them from parent to children while you walk downwards, and after paiting all parental colorings are reverted to "0"

Edited by author 16.06.2026 12:05