```↵
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](https://www.codechef.com/problems/FLIPCOIN) <br/>↵
You can read my commented code for this flipcoin (https://www.codechef.com/viewsolution/4341486)↵
* [MultQ3 Codechef](https://www.codechef.com/problems/MULTQ3) <br/>↵
You can read my commented code for this MultQ3 (https://www.codechef.com/viewsolution/4342905)↵
↵
 <br/>↵
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.↵
↵
<b>Now step two — Thinking how actually this problem is adding in a range problem. </b> ↵
↵
 <br/>↵
<br/>↵
↵
```↵
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).↵
```↵
↵
<b> Step 3 — Adding Arithmetic Progression to Segment Tree using Segment Tree with Lazy propogation. </b> ↵
↵
↵
↵
↵
```↵
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](http://codeforces.com/contest/819/submission/28197900)
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](https://www.codechef.com/problems/FLIPCOIN) <br/>↵
You can read my commented code for this flipcoin (https://www.codechef.com/viewsolution/4341486)↵
* [MultQ3 Codechef](https://www.codechef.com/problems/MULTQ3) <br/>↵
You can read my commented code for this MultQ3 (https://www.codechef.com/viewsolution/4342905)↵
↵
 <br/>↵
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.↵
↵
<b>Now step two — Thinking how actually this problem is adding in a range problem. </b> ↵
↵
 <br/>↵
<br/>↵
↵
```↵
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).↵
```↵
↵
<b> Step 3 — Adding Arithmetic Progression to Segment Tree using Segment Tree with Lazy propogation. </b>
↵
↵
↵
↵
```↵
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](http://codeforces.com/contest/819/submission/28197900)
