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

Автор jomatt, история, 9 лет назад, По-английски

Can anyone please help me to solve this problem, ? (http://www.spoj.com/problems/RRANGE/) I am not good at data structures

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

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

This problem is not about data structures, it's rather brute force involving a little math. You have at most 1000 updates and 1000 queries, so for every query, consider every update and see how it affects the answer.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    but it can be solved with segment tree or BIT?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I wouldn't see the point in compressing the numbers (because N can be as big as 109) and then using a segment tree with complicated queries, when you can solve the problems with only 4 or 5 lines of code and no data structures besides two simple arrays.