jomatt's blog

Spoj problem
By jomatt, history, 11 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

»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    but it can be solved with segment tree or BIT?

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
       
      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