Reading through this DP blog by zscoder — https://codeforces.net/blog/entry/47764
In the "open and close interval" section, the blog explains this problem — https://codeforces.net/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!