Hello fellow problem-solvers. I am writing this post to ask a doubt I am not able to munch anymore. The problem is Double Sum 3 which came as problem F on Atcoder Beginner Contest 390. I am interested to know the knowledge gaps and thoughts which are preventing me from solving this. I don't just need the solution I want if I ever came across a situation remotely matching this, I am at least able to self realize it if not solve it.

My thoughts:

Given the relation $$$\Sigma_{L=1}^N\Sigma_{R=L}^Nf(L,R)$$$, I was not able to come up with anything linear. So I did what is most obvious to me, created a graph out of the problem. Given the test case, I made a graph:

5

3 1 4 2 4

Now in this, starting from 3, if adding values is taken into a group, its contribution is 0 otherwise it forms a group of its own and its contribution is 1. Each value say arr[i] have an edge to arr[i], arr[i-1] and arr[i+1] because if anyone of these are present then no new component is formed. So this is the final graph:

There are 3 disconnected components so the answer for $$$F(1,10)$$$ is 3

The contribution of each index:

$$$[1,1,1,0,0,0,0,0,0,0]$$$

If a node is added and it reduces the number of components like $$$[1,2]$$$ $$$[4,5]$$$ and we add 3 then its contribution is -1 because it reduces our answer.

So now for F(1,3) the answer is 3; F(1,5) the answer is 3 So for $$$\Sigma_{i=1}^NF(i,N)$$$ the answer is the sum of the array contribution across all. For this, across all these are the contributions:

$$$[10,9,8,0,0,0,0,0,0,0]$$$ so the sum of all contributions is 27 and the answer for $$$\Sigma_{i=1}^NF(i,N)$$$ is 27

Now I thought, start from index 1 and start removing the nodes and their contributions and then just sum it as usual. If my sum function is $$$G(start, N)$$$ then I can go from $$$\Sigma_{i=1}^NG(i,N)$$$ so remove the contribution of each index and add it to the sum and I got a net sum the answer.

Removing 1, makes all of its children now to form individual groups and they now contribute +1 more than their usual value. And we can just compute all $$$G(i,N)$$$.

This logic passes all samples and permutation on Atcoder but failed on random tests here.

My code fails for this test case I found after stress-testing:

10

4 1 3 5 2 1 2 5 6 4

Now why this fails? The contribution of node at index 10 will become -1 after removing node at index 1 because its children are still connected by this index shown in the graph below. Now I can run an algorithm to find if the children as still connected by a bridge vertex find that bridge and decrease its value but this seems too much. What am I missing?

I don't know if this happens to higher rated or more extensive problem-solvers or not but I don't want to keep doing this more than this. I used a DSU and a lot of conditions in code which is readable and good but it seems too complex for a solution.