All editorials of CodeChef can be found at https://discuss.codechef.com/c/editorial/5. This is totally free of charge. The only part that is premium is the fact they appear directly on the problem page.

Let us see how to find $$$Score(b)$$$ quickly.

We can see that optimal $$$c$$$ should be $$$[1, 1, \ldots 1, 2, 3, \ldots k]$$$.

Now there should an index $$$i$$$ such that $$$c_i = b_i$$$. Otherwise $$$[1, 1, \ldots 1, 2, 3, \ldots k+1]$$$ could have been a valid $$$c$$$ too. Now it is clear that we only care the largest index $$$i$$$ such that $$$c_i = b_i$$$. So the number of distinct elements in this case is $$$b_i + m - i$$$.

This leads us to the observation that $$$Score(b) = m - \max(0, \max_{i=1}^{|b|} i-b_i)$$$.

Now we have to solve original problem.

Let us just have an array $$$d$$$ such that $$$d_i = \max(0, i-a_i)$$$.

Suppose $$$l_i = \max_{p=1}^{i} d_i$$$.

Now if $$$Score(a[j,i])$$$ is.
1. $$$i-j+1$$$ if $$$l_i < j$$$.
2. $$$i-l_i$$$ if $$$l_i \ge j_i$$$.

$$$l_{i+1} = \max(l_i,d_{i+1})$$$.

So we can see that we just care about how array $$$l$$$ looks after each update.

Let's divide the array $$$d$$$ into $$$sqrt(n)$$$ blocks.

Say we are in some block, and it covers indices from $$$x$$$ to $$$y$$$. After the update, either $$$l_i$$$ $$$x \le i \le y$$$, will be changed to $$$l_{x-1}$$$, other there will be an index $$$z$$$ such that all $$$l_i$$$ $$$x \le i \le z$$$ will be changed to $$$l_{x-1}$$$, and subarray $$$l[z+1,y]$$$ will be unchanged.

So we can update the answer for each block in $$$O(t)$$$, where $$$O(t)$$$ is the time taken to find the smallest index $$$v$$$ greater than $$$x-1$$$ such that $$$d_v > l_{x-1}$$$. In editorial mentioned above, editorialist described the $$$O(logn)$$$ way to find $$$v$$$.

It is possible to find $$$v$$$ in $$$O(1)$$$. It is possible to have a ds which supports update in $$$O(sqrtn)$$$ and query in $$$O(1)$$$.

Now only one thing is left.

How to find $$$\sum_{i=x}^{z} \sum_{j=1}^{i} Score(a[j,i])$$$, given that $$$l_x = l_{x+1} \ldots l_y$$$. It can be found in $$$O(1)$$$.

Here is my $$$O(n sqrt(n))$$$ implementation for reference.