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

LCA со sparse table
Автор Perlik, 13 лет назад, По-русски
Вдохновившись этим постом, решил изучить LCA. За логарифм получилось быстро, но этим методом эту задачу не решишь. Алгоритм с препроцессингом O(N) и ответом на запрос за O(1) не понял, поэтому написал простую sparse table (то есть с препроцессингом за NlogN). Вот мой код, но он почему-то получает WA #3. Может я неправильно написал динамику? Уже и не знаю, что неправильно.
  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Эту задачу имхо лучше и проще решать алгоритмом Тарьяна: http://en.wikipedia.org/wiki/Tarjan's_off-line_least_common_ancestors_algorithm

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я читал этот алгоритм, но он, к сожалению, работает offline, здесь же нужно после каждого запроса знать ответ, чтобы сгенерировать следующий запрос.
    → Ответить