### santa_x112's blog

By santa_x112, history, 3 years ago,

So far I have tried this code but couldn't approach to the optimised way of solving the problem. A small hint would be a great help instead of complete solution.

• +5

 » 3 years ago, # |   +1 Did you solved it ?
 » 3 years ago, # |   0
 » 3 years ago, # | ← Rev. 2 →   0 You can use segment tree to solve this problem. Hint1Use it for the sum and max of range l..r SolutionWhen query asks a range l r you can do the following steps. 1) start with range 1, n2) go both children (you have to go first to left one)3) if your current range is out of required range return 04) if your current range is complete in required range: { MX = max(MX, curMX); return MX*(curR-curL+1)-curSum }5) return sum of children
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I don't think this is a correct solution. (or maybe I misinterpreted it)If I have an array [0,2,4,0] and I want to query (1,4), this solution will yield 10 as answer. (while the answer should be 4)
 » 3 years ago, # |   0 You can try using binary lifting + monotonic stack. :) (Just a hint)
•  » » 15 months ago, # ^ |   0 would you like to share your solution?
•  » » 5 weeks ago, # ^ |   +1 tysm for the hint man, solved it because of that.