Gaajvi's blog

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

someone can help me to solve this problem?

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

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

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

You know?

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

    segment tree isn't algorithm and i know this data structure

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

      ooooo Yes this data structure

      this problem is classic problem segment tree

      if you know segment tree so you can solve this problem

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