PROBLEM LINK:
Setter: Aleksa Plavsic
Tester: Hussain
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Convex-hull Trick, Square Root decomposition
PROBLEM:
Given two Arrays A and B, we have to perform following queries.
- Print maximum element in Range [l, r].
- Add B[i] to A[i] for i in range [l,r].
- Increase B[i] by X for i in range [l,r].
- Increase A[i] by X for i in range [l,r].
QUICK EXPLANATION
- Use Square root decomposition and build convex hull with B[i] as slope and A[i] as intercept.
- Answer block maximum queries in O(1) (amortized) by relying on convexity of B.
- Perform range updates on whole block by considering changes in both arrays before and after last block update separately.
EXPLANATION
This is another long editorial, so, be prepared. 
Here we go!! We will be considering several smaller problems, which will help you solve this problem step by step.
If you don’t know about convex hull, Please read it here and then read. Otherwise editorial will sound like language foreign to you. 
Let us solve a simple problem first.
Problem 1: Given two arrays A and B of length N, perform following two queries on whole array.
- Print the maximum element in A.
- Add B[i] to A[i] for all 0 \leq i \leq N-1.
We can notice that if operation 2 is applied X times, element at position i is B[i]*X+A[i]. Can you relate this problem to Convex hull trick??
Yes, by maintaining a Convex hull formed by one line per position, having slope B[i] and intercept A[i]. We need to find maximum value at a point.
Now, notice that the point to be queried in convex hull is actually the number of times operation two is applied, say X, which is always increasing. So, we can also maintain a pointer CUR_MAX which points to the index of line in hull which have maximum value at X. Whenever we query for maximum, we check only line of strictly higher slope, We can always move pointer to right till it reaches the best line, and answer queries in amortized O(1). (Refer Observation three of convex hull trick article)
Let us consider another problem. (I know all of you can solve it by keeping two variables, and that’s what i need to explain).
Problem 2: Given two Numbers A and B both set to 0 initially.
- Print A.
- Add B to A.
- Add X to A, X given in operation.
- Add X to B, X given in operation.
Try solving this problem using variables addToA, addToB, effectOfBtoA only. Where addToA is sum of all operation 3 performed, addToB is sum of all operation 4.
Click to view
For second operation, just add addToB to effectOfBtoA.
Now, how to print A, Simple, A is sum of addToA and effectOfBtoA. Simple, Right??
Problem 3: Let’s come back to original problem, with just one change, that we perform all operations on whole array, not on a specified range.
Now, try solving this problem.
Woah, this is just the combination of above two problems we just solved. We make a convex hull, and answer maximum element according to original arrays A and B as given in input, and just ad to it the changes made by Third and fourth operation.
How?? Notice that if effect of initial values of array B on array A are handled by convex hull.
The effect of changes due to third and fourth operation on array can be calculated as effectOfBtoA + addToA.
So, answer of this problem is answer of first problem + effectOfBtoA + addToA.
Does this rings the bell for whole solution, if we use Square root Decomposition and all queries are such that no block is partially covered??
Yes, we can just solve this problem by considering each block separately as solving Problem 3 Number of Block times, and output the answer which is maximum among the answer of all these blocks.
Yes, that all we have to understand. But, we have to keep certain things while handling partially covered blocks.
Important things while implementing this problem
When blocks are partially covered, we just have to rebuild the build the convex hull, may also be required to sort the lines if slopes of lines are changed, update the combined impact of operations performed on whole block since last update.
This all can be done, solving second problem as mentioned above, for each block, where only the operations covering whole block are considered. When lines are updated with effect of these, remember to set all 3 variables as zero.
For answering queries over whole block, consider it just the Problem 3 and answer using CUR_MAX pointer.
For implementation, refer solution links below. (Editorialist’s solution is commented line by line).
I tried to convey all important ideas in short, so as to keep length of editorial reasonable. If anything’s unclear, feel free to ask in comments.
Also, share your ideas/approach, if they differ or are informative.
Time Complexity Analysis:
Since each border block can take at most O(B) size. All operations can take atmost O(\lceil{\frac{N}{B}}\rceil). For appropriate value of B ~ \sqrt{N}, The Time complexity comes down to O(N \sqrt{N}) if we ignore the sorting cost of lines initially.
AUTHOR’S AND TESTER’S SOLUTIONS:
Editorialist’s solution (Commented Code)
Until Solutions are not linked by Admin, you may refer my solution at this link.
Feel free to Share your approach, If it differs. Suggestions are always welcomed.