So much overwhelmed while writing this, but it's like my college dream accomplished. I always wanted to see myself in purple and currently witnessing this moment is a very special feeling to me.

Thanks to all who constantly supported me during this journey, specially satyam343 for constant guidance and motivation fahad_,AkshunyaVijayvargiya for Icpc team support, although we didn't make it to regionals. greensignal for listening my BT many times.

Never witnessed back to back atleast a week gap in div2 contests on Codeforeces earlier which is becoming so common these days.

I have 2 kind of operations

Update the value of all vertex in a subtree of a vertex to 1.

Update the value of all vertex which are ancestors of a vertex to 0.

I m not able to think how to do the 2nd operation in log(n) using segment tree with lazy Propagation.

Please anyone let me know your approaches.

Thanks in advance.

The first thought we should get here is that,

We will try to find the number of moves if we want to explode from ith index,and then we will take the minimum for all i from 1 to n.

Now, for each index i we have to calculate the number of moves required in O(1) or O(log(n)).

My solution deals with this in O(1) so I will explain that,

Ideally before exploding at index i, what we have to do is to make the array strictly decrease from index i to n (except for the fact that we will not decrease any element beyond 0) and strictly increase from index 1 to i (here also we will not decrease any element beyond 0) because this will be the case when the chain reaction will eat all the elements.

Now, since elements to the left of index i and to the right of index i are independent now , we will check for them separately.

Now let us try to find the number of moves required to make the array increasing from index 1 to i.

To do this in O(1):

We want to know 2 indexes say i1 and i2 :

1. i1 will be the index from where we have to make all the elements equal to 0 all the way to 1st element. so i1=max(1,i-a[i]).

1. now to explain what i2 will be

   suppose a case:

   1 2 3 11 12 9

   if we want to explode at the 6th element we will start decreasing the elements from the 5th index but look carefully we don't have to decrease elements beyond 4th element as they are already smaller, so the final array will look like

   1 2 3 7 8 9

   so in total, there will be a total (12-8)+(11-7)=8 moves required before exploding.

   So,i2 will tell the 1st index to the left of index i from which we don't have to further decrease elements to make the array increasing from index 1 to i.

We can find i2 using stack datastructure for each index i, How?

Suppose we want to calculate i2 for i so,

a[i]-(i-i2)<=a[i2] should hold,

i.e

a[i]-i<=a[i2]-i2

So, using stack we can find i2 for each index i from 1 to n in total of O(n)... (i.e. avg O(1) for each index i) by :

(suppose S is our stack of integers containing the indexes of orignal array)

S.push(1);

for(i=2;i<=n;i++){

while(S.size() && a[S.top()]-S.top()>a[i]-i){

                  S.pop();

         }

    i2=0;      // i2=0 means , there isn't any valid i2 from 1 to i-1.

    if(S.size()) i2=S.top();

    S.push(i);

}

Now there will be 2 cases :

i1<i2 :

In this case, the Number of moves required to make the array strictly increase from index 1 to i will be

  (number of moves to make the array strictly increasing from index 1 to i2) +

  (number of moves to make the array strictly increasing from index i2+1 to i)

  we will be storing the number of moves required to make the array strictly increasing from index 1 to index i
  so we will get (number of moves to make the array strictly increasing from index 1 to i2) in O(1).

  Also,
  To calculate  (number of moves to make the array strictly increasing from index i2+1 to i) in O(1)
  we will maintain a prefix sum array of a[j]-j say pre1 (the name of this prefix array).

  So,

  (number of moves to make the array strictly increasing from index i2+1 to i) =

  (pre1[i-1]-pre1[i2])-(i-i2-1)*(a[i]-i).

i1>i2 :

In this case, Number of moves required to make the array strictly increase from index 1 to i will be

  (number of moves to make the array strictly increasing from index 1 to i1) +

  (number of moves to make the array strictly increasing from index i1+1 to i)

  To calculate 

  (number of moves to make the array strictly increasing from index 1 to i1)

  we just want the sum of elements from index 1 to index i1
  which we can easily get by keeping another prefix sum array of a[j]'s 
  because we have to make all the elements equal to 0 from 1 to i1.

  Now,
  Calculation of (number of moves to make the array strictly increase from index i1+1 to i) is already described in above 
  case of i1<i2.

  i.e

  (pre1[i-1]-pre1[i1])-(i-i1-1)*(a[i]-i).

So finally we have got the number of moves required to make the array increasing from index 1 to index i in O(1). A Similar thing, we can do to find the number of moves required to make the array decreasing from index i to index n.

Now we can just explode at ith index with power a[i] so in total we will have to expend

a[i]+(number of moves required to make the array increase from index 1 to index i)+(number of moves required to make the array decrease from index i to index n).

And hence in O(n) we can find the minimum :)

solution -> https://mirror.codeforces.com/contest/1795/submission/193942204

I hope this helps.