Open-and-close-interval DP doubt

Revision en1, by venti, 2021-04-18 10:11:31

Reading through this DP blog by zscoderhttps://mirror.codeforces.com/blog/entry/47764

In the "open and close interval" section, the blog explains this problem — https://mirror.codeforces.com/contest/626/problem/F

The explanation says -

"Suppose there are j open sets. When we add a[i], the sum a[i] - a[i - 1] will contribute to each of the j open sets, so we increase the current imbalance by j(a[i] - a[i - 1])."

But doesn't this imply that all j open sets contain a[i-1]?

Shouldn't the correct net increase in imbalance be - sum(a[i] - max(cur_open_set)) // (assuming we somehow tracked the max for each cur_open_set)

But for my equation to be equal to j*(a[i]-a[i-1]), all the current open sets would need to have a[i-1] in them. So how does this work?

Or is it that: these open sets are each in different possibilities, and we only track 1 open set per possible-way-of-counting? But that can't be true either, since then I'd only have contiguous subarrays as groups in each possibility I think. Can someone clear this up for me?

Please help! Thanks!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English venti 2021-04-18 10:20:28 300 (published)
en1 English venti 2021-04-18 10:11:31 1158 Initial revision (saved to drafts)