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 indexLis connected to the left andX=0 denotes otherwise. Similar argument forRandY.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 connectMtoM+1or 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