You start with an array containing all zeroes. You will be given some updates. Updates are in the form $$$L, R, A, B$$$. For each update, you have to add $$$A+(i-L)*B$$$ for each $$$L \leq i \leq R$$$. You will have to answer queries in the form $$$L, R$$$. For each query, you have answer what's the maximum element in $$$[L, R]$$$ range.
The range sum query version of this problem can be solved with segment tree with lazy propagation. However, I can't think of a way to solve this one.
Problem link please?
https://codeforces.com/contest/436/problem/F
Maybe lichao tree? I don't have a idea.
This can be solved with normal sqrt decomposition.
For each query $$$L, R, A, B$$$, lets say that $$$A - L * B$$$ as a const value and now the remain problem is only adding $$$i * B$$$. If we assume that each element is a line with slope $$$i$$$ then the problem become finding $$$max(f(i) = i$$$ * (sum of B + const values that have been updated on it $$$))$$$.
Assume that before each query, we have built a convex hull for each blocks. If the current query only conflicts but not covers a block, just update all the element in that block and build its convex hull again. Or else, simply maintain a lazy const and lazy sum of B.
Then for each query asking for maximum in $$$[L, R]$$$ range, if it covers a whole block, ask for the best line for $$$lazy$$$ B plus the $$$lazy$$$ const value. If it just conflicts but not covers a block, we can iterate over the conflicting elements.
P/S: As lazy B only increases, and the sorting the lines again for each reset is not necessary cause the slopes are const, I think this is doable in $$$O(N$$$ $$$*$$$ $$$sqrt(N$$$$$$))$$$.
So, if $$$B$$$ can be both positive and negative, we may need to maintain the convex hull dynamically?
Not really. Since we do not have to insert or delete a line from the hull, dynamic convex hull (if I do not misunderstand what u said) is not necessary. Instead, you can just implement casual convex hull and binary search for each lazy B instead of using an increasing pointer like when B is positive.
It took me a lot of time, but I finally understand now. Since the lines are fixed, we know the intersection points in the convex hull. So we can find the optimal line with binary search for some $$$x$$$.
Thanks for your reply.
（Sorry. Misread the statement.）
You can solve by SQRT-Decomposition. For each block you are able to maintaina convexhull Updating and querying will be solved easy in O(Nsqrt(N))
Can you please provide a link to the problem?
https://codeforces.com/contest/436/problem/F
I have tried to code the Solution.
The solution is working for 32-bit numbers. I have made appropriate comments if need be to use it for 64-bit numbers.
As of now I have considered that B can be positive or negative. Thus the time complexity is $$$O(sqrt(N))$$$ per update and $$$O(sqrt(N) * log(N))$$$ per query. Hence making overall complexity $$$O(Q * sqrt(N) * log(N))$$$
If $$$B$$$ is always non-negative than we can reduce the $$$log(N)$$$ factor from query thus it would result in complexity $$$O(sqrt(N))$$$ per query. Thus overall complexity becomes $$$O(Q * sqrt(N))$$$. I have made appropriate comment in the code to change if $$$B$$$ is non-negative (Change the binary search of convex hull trick query to linear one).
I realised lately that my code works on similar idea as suggested by ngfam. Let me know if I am in wrong direction.