Gaajvi's blog

Spoj problem
By Gaajvi, history, 11 years ago, In English

someone can help me to solve this problem?

  • 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

You for solve this problem should know algorithm ("segment tree") :))

You know?

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

I think it is Mo algorithm ( sqrt decomposition ). You can read about it ;)

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

You can solve this problem using segment tree in witch every node is a multiset. Then the build complexity will be O(Nlog(N)), because the tree is balanced. And each query and update will be done in O(log^2(N)).

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

    Please, describe me how you will find sum for theravada second query ? I solve some problems with segment tree, but I never solve something like it.

    About my solution, now I am not pretty sure( because we have update), but some sqrt decompostion should be good.

    → Reply