santa_x112's blog

Need help in solving Increasing Array Queries CSES
By santa_x112, history, 3 years ago, In English

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.

Link to the problem : https://cses.fi/problemset/task/2416

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Did you solved it ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

see dolphingarlic's explanation + solution

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can use segment tree to solve this problem.

Hint1
Solution
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can try using binary lifting + monotonic stack. :) (Just a hint)

→ Reply