This was the fourth question in the November Lunchtime. I am not able to understand it, even after reading the editorial. Can someone please explain it in a bit more detail?
Contest link Problem Link Official Editorial Link Unofficial Editorial Link
I can not udnerstand anything in the official editorial.
I can't understand the dp states in the unofficial editorial, and also how to use the treap data structure being discussed in the editorial.
Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).
You don't need a treap, a segment tree works fine.
DP[L][R][X][Y] denotes the min cost to connect the interval [L, R]. X=1 denotes index L is connected to the left and X=0 denotes otherwise. Similar argument for R and Y.
Now, each node of the segment tree stores DP[L][R][X][Y], for 0 <= X, Y < 2, for the range [L, R] corresponding the node of the segment tree. Consider the index M = (L+R)/2. You can choose to either connect M to M+1 or not. Handle both cases separately and merge the 2 DP values from left and right children to get the DP value for the current node. See my code for more details.
My code