1 Тема от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Тема: disjoint set

Тут проскочила интересная фраза.
http://e-maxx.ru/algo/dsu

Эффективная реализация для задачи минимума в автономном режиме
(т.е. нужно реализовать структуру данных, которая позволяет добавлять элементы из множества {1,..,N} и извлекать минимум; задача автономна в том смысле, что вся последовательность запросов известна к началу выполнения алгоритма)

Подозреваю она из Кормена, но уже мозги вспухли от идей, как применить DSU к поиску минимума, при чем за &O(1)
И вообще если такое возможно, тогда возможна сортировка за линейное время (что как известно в общем случае не возможно)

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: disjoint set

Ссылка не стоит, но вот есть статья по этому поводу:
http://e-maxx.ru/algo/rmq_linear

Подозреваю она из Кормена, но уже мозги вспухли от идей, как применить DSU к поиску минимума, при чем за &O(1)
И вообще если такое возможно, тогда возможна сортировка за линейное время (что как известно в общем случае не возможно)

Ну одно дело _находить_ минимум, а другое - находить и _извлекать_ его из массива. Без этого сортировку не сделать. Так что противоречия тут нет.

Сайтe-maxx

3 Ответ от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Re: disjoint set

e-maxx пишет:

Ссылка не стоит, но вот есть статья по этому поводу:
http://e-maxx.ru/algo/rmq_linear

Не нашел там ни слова про disjoint set

4 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: disjoint set

А, забыл дописать. Фарах-Колтона-Бендера действительно не использует dsu, и вообще он отвечает на запросы в онлайне. Но есть гораздо более простой алгоритм Тарьяна, который основан на dsu, и отвечает на запросы lca в оффлайне.

Как непосредственно применить dsu к задаче rmq, без сведения к lca, не знаю.

Сайтe-maxx

5 Ответ от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Re: disjoint set

e-maxx пишет:

Но есть гораздо более простой который основан на dsu, и отвечает на запросы lca в оффлайне.

Как непосредственно применить dsu к задаче rmq, без сведения к lca, не знаю.

Я правильно понял, что в нашей дискуссии есть мысль, что на запросы min(L,R) в оффлайне можно (хоть и через большой геморрой с сведением к lca) отвечать за О(1) ???

6 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: disjoint set

Ну да.

В этом результате, кажется, нет ничего удивительного - с предпосчетом n log n (sparse-table) отвечать на такие запросы за O(1) вообще легко. Это же более мощный метод, и у него предпосчет за n.

Сайтe-maxx

7 Ответ от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Re: disjoint set

e-maxx пишет:

Ну да.

В этом результате, кажется, нет ничего удивительного - с предпосчетом n log n (sparse-table) отвечать на такие запросы за O(1) вообще легко.

Ну да, и с предпосчетом n^2 (stupid-table smile ) отвечать за О(1) еще легче smile

e-maxx пишет:

Это же более мощный метод, и у него предпосчет за n.

Да, вот это и заинтересовало (препроцессинг за линейное время). Но, подозреваю, что эта метода применима в жизни, но не применима на контестах. Так как писать ее относительно трудоемко.

8 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: disjoint set

Да, я за 5 лет занятий олимпиадами ещё не встречал задачи, где надо было бы делать LCA или RMQ за O(1) с линейным препроцессингом smile

Сайтe-maxx