prob : http://codeforces.com/contest/935/problem/F

I have read the editorial but didn’t understand it. Please someone help me!

prob : http://codeforces.com/contest/935/problem/F

I have read the editorial but didn’t understand it. Please someone help me!

Which part of the editorial u couldnt understand?

truely speaking i didn’t understand both the implementation part and how the expression comes? (that min(…, 0))

Ohk ,

So let us see this differently.Instead of considering the array elements ,we would be dealing with differences . Lets say we have a diff array,where diff[i]=arr[i]-arr[i+1].

Lets calculate the ans ,lets say it is ans

Now for query of type 1:

Lets say an index i exists in (l,r) such that diff[i-1]<=0,diff[i]>=0 (means ai>=ai-1 and ai>=ai+1)

So in such case we can increase ai,so that ans increase by 2*x(this is the best u can get)

Eg: 3 5 2,increase 5 by 2,u’ll see the change as 4(if u want proof ask)

So this is equivalent to finding local maximum(u can easily find it using sets/map just insert all valid i for which that condn is true and binary search to see if any element lies in range l,r)

Now lets say there is no element in range for which local maximum is true.

So there can be atmost 1 local minima.

Proof: if there were 2,then there had to be a local maxima b/w them which is a contradiction

So lets say there is an index i at which there is local minima.

If u try drawing graph,it would be somewhat like this:-

```
\ /
\ /
\ /
.
i
```

So now lets consider all indices in range[l,r] !=i

So lets say that index is j

Now u can notice for this graph,1 of the following would be true

1)aj-1 < aj < aj+1

2)aj-1>aj>aj+1

So lets consider the first case

And denote them as b,a,c

So b < a < c

So initVal=(a-b)+(c-a)=c-b

Now we add x to a,so finalVal=(a+x)-b+mod((a+x)-c)

If a+x<c u’ll find finalVal=initVal,else the same as editorial.

Similarly we have to calculate for i,u can prove that

If both minima and maxima doesnt exist then it will be increasing or decreasing graph,for which calculating formula is easy.

Now comes update,as i said earlier i am dealing with differences.

So if i increase l,r diff[l-1],diff[r] are the only ones that will change so update those in segment tree.

(If u see editorial they say to update 4 things,thats becaz they need to calc ci-ai,and bi-ai,so see what u need to calculate and accordingly do like if ur diff arr was diff[i]=arr[i]-arr[i-1],u would need to update l,r+1(probably u’ll need both kind of diff arr))

Edit:

Here’s my ac code with implementation of above(just in case if someone requires):-

3 Likes

“If a+x<c u’ll find finalVal=initVal,else the same as editorial.” If you don’t mind can you please explain how that expression(2*max(0, x-(ck-ak)) comes? Actually I am not clear how they are sure about max because the value (current_val - initial_val) may be positive or negative.

Ohk so we have initval=c-b,finalVal=a+x-b+mod(a+x-c),if(a+x)<c,mod(a+x-c)=c-x-a

So finalVal=a+x-b+c-x-a=c-b

So increment =0 -------(1)

Now if a+x>c

Mod(a+x-c)=a+x-c

So finalVal=a+x-b+a+x-c=2a+2x-b-c

So increment=finalVal-initVal=(2a+2x-b-c)-(c-b)=2a+2x-2c =2*(x-(c-a))-----(2)

From (1) and (2)

=max(0,2*(x-(c-a)))

1 Like

how can we take the max? as it is case dependent i.e. when we have incremented ‘a’ then we have no control whether 1st condition holds or the 2nd one. so, why max?

Lets say first case comes,a+x<c

So x-c+a=-ve

So max(0,2*(-ve))=max(0,-ve)=0

If second case comes a+x>c

X+a-c=+ve

So max(0,2*(+ve))=2*+ve

1 Like

sorry for the late reply! I am busy with my internals

Last thing i want to ask : can you please explain the implementation approach a little bit more. More specifically how to answer : “2·max(0, x - (ci - ai)) - 2·min(bi - ai, x)”

For this u can find local minima ,similar to how we found local maxima(using map),lets say u got i.So diff[i] and diff[i-1] would be those differences(ci-ai,bi-ai)…

1 Like

if possible can you please look into my code : http://rextester.com/NUP69259

It is giving WA on test 22.

U got the mistake?

sadly no

have you looked into the code? If yes can you please suggest me where i can shorten the code? Because i’ve seen three or four solutions and all of them are pretty short (but sadly didn’t understand the idea of implementation)!

Actually i have my exams tomorrow,i will surely see when i am free

thanks mate and good luck for the exams!

I too have seen many code.Some codes i saw had a worst case complexity of O(N) per query yet still they passed,and some didnt use the diff array and instead worked on original array (bt that was more difficult to understand for me)

2 days to go ,on saturday