Hi, let me explain the 4th problem. let’s make a couple observations:
1.If we have two connected segments that have a common part [a..b] [x..y], we can create two segments that have no common part with connections between their first and second ends respectively.
2.It gives us next idea(let’s sort our set, and divide it into connected groups), but if the size of a connected group \ge 4 we can split into two groups of sizes [group/2] and group-[group/2], the answer will be smaller, and every number will be connected.
3.Let we have order of set A[1..N], DP[1..i] - the minimal cost to connect prefix A[1…i],
DP[2] = A[2] - A[1]
DP[3] = A[3] - A[1]
DP[x] = min(DP[x - 3] + A[x] - A[x - 2], DP[x - 2] + A[x] - A[x - 1]),
we checking where to connect x \implies to x-1, or to x-2.
Let’s rewrite that DP, DP[i][j] denotes connection of the prefix 1..i, j=0 denotes that i is connected to 1..i-1, j=1 denotes that i should be connected to i+1.
DP[i][1] = DP[i-1][0], DP[i][0] = min(DP[i-1][0],DP[i-1][1])+A[i]-A[i-1], for i \ge 3.
But how to maintain add/erase queries? Let’s make one more observation we can keep DP for the segment l..r in a similar way:
DP[l..r][i][j] (r-l\ge1) denotes minimal value to connect everything in the segment l..r, if i=1, l should be connected to l-1, otherwise it’s connected to the segment l..r.
If j=1, r = should be connected to r+1, otherwise connected to the segment l..r.
For r-l==1 and r-l==2 better to recalculate DP with hands.
For r-l \ge 3, we can split segment into to l..m, and m+1..r, and recalculate DP[l..r][x][y] as min(DP[l..m][x][i] + DP[m+1..r][j][y] + (1 - i) * (1 - j) * (A[m + 1] - A[m])).
Only in one case we don’t need to take A[m+1]-A[m], if A[m] is connected to l..m and A[m+1] is connected to m+1..r. We need to add some data structure for the solution, we can use cartesian tree/splay tree, but it’s very painful to write that, (I did it, I know what I’m saying about 
)
Let’s use implicit segment tree(also, we can read all queries, compress the values and use normal segment tree) and for each node to save (min and max on the segment in the segment tree, dp[2][2] and other things), after that we can combine two segments into one, by operations as described above.
We have a solution with complexity O(Q log N) but with huge constant around (~log N). My solution with cartesian is very hard to understand, you can write yours, maybe my debugging solution will help understand what’s going on: //Let we have sorted array x, and want to recalculate DP#include <bits/stdc++. - Pastebin.com
missed that…