jomatt's blog

Spoj problem
By jomatt, history, 8 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    but it can be solved with segment tree or BIT?

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

      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.

      → Reply