pro.algorithms
Подскажите, как можно решить следующую задачу? Есть 10⁵ запросов вида
добавить строку в список, либо получить k - ый элемент списка при условии, что строки отсортированы. Ограничение 1250 мс.
16 ответов
Ничего лучше дерева поиска для этой задачи, кажется нет
Дон
Кинг
Автор вопроса
AVL?
Любое балансирующеся
Декартач с размерами поддеревьев для динамического поиска k-ой порядковой за log, если нужно быстро написать
Можно написать бор, он будет отвечать на каждый запрос за длину строки
Дон
Кинг
Автор вопроса
Можно написать бор, он будет отвечать на каждый за...
А k - ый получать через обход in_order?
Если k фиксированное, то можно кучу создать на к элементов) и нужный элемент всегда в вершине будет
Если k фиксированное, то можно кучу создать на к э...
ну это должно быть хуже чем бор если строки за линию сравнивать
ну это должно быть хуже чем бор если строки за лин...
Ты прав. Не обратил внимание, что со строками работаем
будем поддерживать декартово дерево и сравнивать строки с помощью хэширования за log n, итого O(S + q log S log q), где S - суммарная длина строк
будем поддерживать декартово дерево и сравнивать с...
Можно делать встроенным сетом, переписав компаратор на свой
Можно делать встроенным сетом, переписав компарато...
можно, да, только не встроенным, а из pb_ds
можно, да, только не встроенным, а из pb_ds
Да, забыл, что дефолтный сет не умеет обращаться к случайному элементу :(
Trie проще всего, с хранением количества потомков для каждого элемента. Тогда поиск и по элементу и по индексу log(n)
Лог откуда?
Кажется у трие даже не лог, а длина ключа.
Похожие вопросы
Обсуждают сегодня