Problem Setter: xodiac
Difficulty: Medium-Hard
Prerequisites: Square root decomposition, Convex Hull Trick
Explanation:
Question is to find maximum chocolates in exchange of x coins. Given a set of lines of form Y=A*x+B, the question is to find the maximum value of Y for a given x.
We will use Convex Hull Trick to find the maximum value of Y i.e chocolates.
Divide the array into sqrt(n) blocks . We will maintain a CHT for each block.
For query 1 : To remove an element you can find the block in which the element is present in sqrt(n) time. It will take an order of sqrt(n) time to remove the element from that block as the size of each block is sqrt(n) . Similarly, for inserting an element it will take order of sqrt(n) time .
After removing and inserting an element we will need to update the CHT for corresponding blocks. It will take sqrt(n)log(sqrt(n)) time to rebuild the CHT for corresponding blocks .
We will need to rebuild the whole square root decomposition after sqrt(n) queries of type one as in worst case it may be possible that the number of elements in a block becomes equal to n. If we rebuild then the number of elements in a block will not exceed 2sqrt(n).
For query 2 : To answer the query of second type we will iterate the blocks which lies completely between the given range [L,R] and brute force for starting and ending blocks. It will take sqrt(n)*log(sqrt(n)) time .
So the overall complexity will be q*sqrt(n)*log(n)
Author’s Solution: click here
Tester’s Solution: click here