I am not able to solve this problem.

I tried to understand the editorial.

I didn’t understand how can we use stl set to find the nearest to the left and to the right destroyed number.

Also, if there is another approach please explain to me.

I am not able to solve this problem.

I tried to understand the editorial.

I didn’t understand how can we use stl set to find the nearest to the left and to the right destroyed number.

Also, if there is another approach please explain to me.

This problem can be solved using DSU (Disjoint Set Union). If you are not familiar with it, you should definitely study it first, otherwise, keep reading.

The idea is to answer questions in the reverse order. At first all the numbers are destroyed so the answer is 0. Now restore the numbers in the reverse order (go back in time kinda). Everytime we restore a number make a set that contains this number. Let’s say this number has value x. Then check if x-1 and x+1 are destroyed or restored. If they are restored then do union_set(x, x-1) or union_set(x, x+1). So everytime you restore a new element, you either create a new set which contains only that newly restored number, or you add this number to an existing set. In either case, find the new sum for the set, and compare it with the previous maximum sum which is the answer to the previous query.

**Example.**

Let’s look at the first example, the input is:

4

1 3 2 5

3 4 1 2

So let’s solve the problem in the reverse order. We need to output ans[i] for each i from 1 to 4.

It is clear that ans[4] is 0, since all the numbers will be destroyed and the array is empty.

Now (in the reverse order) the next number is the 2nd element which is 3.

So ans[3]=3

Now the next number is the first number which is 1. Since numbers 1 and 3 are next to each other they can be in the same subarray. Thus, we do set_union(1,2), the first and the second number (which are 1 and 3 in value). We also keep track of the sum of a set. So in this case, we have only one set {1, 3} with sum 4 so that will be the answer.

ans[2]=4

Now the next element is the fourth element which is 5 in value. Index 4 is next to 3 but index 3 is still destroyed so it means that we need to create a new set {5}. Its sum is 5. Compare it to the previous maximum. 5>4 so:

ans[1]=5.

Let me know if something is not clear.