It's brilliant! Thank you bicsi, this is a really neat solution.

I have another solution to this problem that may work

Use f[i][j]=X to represent the X extra segments are needed to cover from i to i + 2^j Use g[i][j]=Y to represent when adding f[i][j] extra segments after segment i, the actual terminating node is Y.

DP to calculate f, g, then loop every starting node and lookup f, g to calculate the answer in logK. Go through this process and reverse all segments to do it again, to cover the case that first extra segment is not starting from i_right

I think the prerequisite of sliding window is: if you move head or tail, middle solution doesn't change. Which might not be true in this problem

How are you going to handle the case that one extra X covers multiple intervals? Also, when the head of sliding window changes, all the extra X in the middle might change.

Auto comment: topic has been updated by Mopriestt (previous revision, new revision, compare).

Auto comment: topic has been updated by Mopriestt (previous revision, new revision, compare).

Oh,I smelt some special tricks..

Surprised to see Chinese character^_^

(with sniper precision)!

Div1..not Div2

For div1 B...I tested the case#3 on my PC and the answer is correct,but the result is different on CF..

Ok I got it,sorry for annoying.I thought it only a private space...