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

Количество различных чисел на отрезке
Автор alibi, 10 лет назад, По-русски

Всем привет!

Как найти количество различных чисел на отрезке, с помощью "дерева отрезков"? Я нашел коммент на e-maxx, но не понял как строиться само дерево. Буду рад если разъясните =)

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

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

Персистентность FTW ~
Почитай такое

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

Знаю решение за NlogN памяти и logN на запрос(log^2 ?).

Построим массив Next[i] = j, j — первое такое, что a[j] = a[i]. Возьмем самое правое вхождение какого-то числа в отрезок, чем оно отличается от других вхождений? Правильно, для него next > R. Построим дерево, в вершине будем хранить set элементов. Ответом будет количество элементов которые больше R.

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

    да, log^2, конечно

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

      Можно ещё прикрутить технику частичного каскадирования (fractional cascading), тогда будет online решение за O(log(n)) на запрос.

      Про это можно прочитать:

      Недавно вот здесь обсуждалась задача DQUERY со SPOJ.

      Персистентное ДО — это здорово. Но я не знаю как его легко адаптировать, если в задаче будут запросы изменения элементов. С обычным деревом отрезков декартовых деревьев это решается легко.

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

Как-то так

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

Тут

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

Всем спасибо. Получилось!)

→ Ответить