Hello Guys…

This time I’m not posting any editorial because of an unavoidable reason (not being able to solve any problem complete ), but i still invite you all to share your approach for any of the four problems.

Even then, some of the users have shared their approaches for various problems, which are mentioned below:

**SMRSTR**

This problem has been discussed at here by @vipin_bhardwaj

**SHUFFL**

This problem has been discussed here by @aayushkapadia

**L-R Queries** using sqrt decomposition by @avi224

Break the array into blocks of size \sqrt{N} and then use a map containing frequencies of numbers in each block. For update, remove A[l] from the block containing index l( i.e. l/block\_size) by decreasing its frequency and then add y to it.

The key to solving the problem is to notice that we have to minimize the quadratic expression (x-A[l])*(x-A[r]) such that x=A[m] and l\le m \le r. Note that the global minimum occurs at x_0=0.5*(A[l]+A[r]). We have to find this A[m] nearest to x_0. This can be done using binary search **(lower_bound() function in c++)** on the frequency maps.

For query, just iterate from l onwards and calculate normally until you find the start of a block. Iterate through every block as long as index r is outside the block, and find the nearest A[m]. After the last block, calculate normally until index r is reached.

The preprocessing part takes O(N*log(N)) and complexity is O(\sqrt(N)*log(N)) per query.

Refer to solution here

**STRQUER**

All credits to @mgch, the setter of this problem. (I can call this one as Official Editorial) (Copied from answers)

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[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: https://pastebin.com/PuFTvuNy

And i hope you guys would like to share your approach as always.