Блог пользователя santa_x112

Автор santa_x112, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Did you solved it ?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can use segment tree to solve this problem.

Hint1
Solution
  • »
    »
    3 года назад, # ^ |
    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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