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

Spoj problem
Автор Gaajvi, история, 9 лет назад, перевод, По-русски

someone can help me to solve this problem?

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

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

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

You know?

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

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

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

      ooooo Yes this data structure

      this problem is classic problem segment tree

      if you know segment tree so you can solve this problem

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

Автокомментарий: текст был переведен пользователем Outsider (оригинальная версия, переведенная версия, сравнить).

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

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

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

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)).

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

    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.

    → Ответить