How to Solve This Data Structure Problem

Revision en1, by solaimanope, 2019-10-30 12:17:51

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English solaimanope 2019-10-30 12:17:51 512 Initial revision (published)