PLEASE INCREASE BRIGHTNESS IF IMAGES ARE NOT CLEARLY VISIBLE. POOR PHONE CAMERA . APOLOGIES
If your are familier with concept of Segment Trees with Lazy Update, Please go ahead and read the solution.
If not, please do these two classic simple problems of Segment Trees with Lazy Update on Codchef.
Then come back to this problem. This problem is a classic implementation of Segment Trees.
Purpose of this tutorial is to help you find your solution and not just giving the solutions.
Your code here...
- Flipcoin Codechef
You can read my commented code for this flipcoin (https://www.codechef.com/viewsolution/4341486) - MultQ3 Codechef
You can read my commented code for this MultQ3 (https://www.codechef.com/viewsolution/4342905)
Now we will consider with above example. Hope this example is self explanatory. Now think how you can exploit this concept of adding a value in a range. Try yourself. Think in terms of segment tree.
Now step two — Thinking how actually this problem is adding in a range problem.
Consider example —
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10<br/>
8 3 5 7 4 9 10 1 2 6 <br />
Think all the case i.e. in what range we add to what values. ? Try yourself. <br/>
Case 1. p[i] >= i <br/>
Take p[4] = 7<br/>
for shift id Id0 Id1 Id2 Id3 Id4 Id5 Id6 Id7 Id8 Id9<br/>
value which is to be <br/>
added --> 3 2 1 0 1 2 3 6 5 4<br/>
<br/>
(hope you understands this. !!!!) bingo go ahead...<br/>
deduction now <br/>
<br/>
Case 1.1 We have to add values (3, 2, 1, 0) for shift id range (0, 1, 2, 3)<br/>
Case 1.2 We have to add values (1, 2, 3, 0) for shift id range (4, 5, 6)<br/>
Case 1.3 We have to add values (6, 5, 4) for shift id range (7, 8, 9)<br/>
Case 2. p[i] < i <br/>
Try yourself. Code will help. Code is commented. Please see if you are struck. <br/>
So now we have to add a arithmetic progression in some range in a segment tree. Adding some value to Segment tree is direct problem. Now think how we can add AP to ST. Before going to this, please evaluate what must be final answer and time complexity.
Since leaves store the value which are added to a particular shift. Like 1st leave store value to be added for 0 shift. 2nd leave store value to be added for 1st shift. Hence we need to take the minimum of all leaves. Therefore query segment tree once in the end. Updating Segment tree is O(Logn) Total time complexity O(nLogn).
Step 3 — Adding Arithmetic Progression to Segment Tree using Segment Tree with Lazy propogation.
``` Now, consider a segment tree with 0-7 as nodes. i.e. it means we have shift id from 0 to 7. leaves represents value to be added for shift id 0,1,2,3...,7.
Now if we have updation query to add values (0,1,2,3) in range (2,5) of segment tree. Refer to above diagram. we are splittng range (2,5) in two parts 1. range(2,3) 2. range(4,5) ie there are 4 nodes and 2 nodes in both left & right tree. So, value(0,3) also has to be splitted in same way. So Left Tree range(2,3) value(0,1) Right Tree range(4,5) value(2,3).
General formulae :- we have range(l,r) in which we have to update. value as (valueLeft, valueRight) values to be updated (a,b) current range in our segment tree
N = number of nodes in (l,r) = r - l +1
this N also is number values in AP in (valueLeft, valueRight)
valueLeft + (N-1)*Difference = valueRight
Difference = (valueRight - valueLeft) / (N-1). //Corner case if N==1.
so now we have to split (l,r) in two parts having
Leftnodes = (a+b)/2 - l + 1
Rightnodes = (r- (a+b)/2).
(valueLeft,valueRight)
|
---------------- | ----------------------
(valueLeft, valueLeft+(Leftnodes-1)*Difference ) (valueLeft+(Leftnodes)*Difference, valueRight)
```
My solution with comments :- Accepted Submission
