В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1611 membersпожаловаться на группу
2020 April 13

f

fashdrag (VladKov) in pro.algorithms
Kotomord_λapki
разверните, плиз
Знаю как находить k-ую порядковую статистику на на отрезке [l,r] через перс ДО
Не могу написать как находить k-ую порядковую статистику на пути от u до v в дереве, где к каждой вершине приписано значение
источник
17:25пожаловаться#1

K

Kotomord_λapki in pro.algorithms
это нужно в цикле делать?
источник
17:30пожаловаться#2

K

Kotomord_λapki in pro.algorithms
можно полное условие?
источник
17:30пожаловаться#3

f

fashdrag (VladKov) in pro.algorithms
Какой еще цикл?
источник
17:31пожаловаться#4

f

fashdrag (VladKov) in pro.algorithms
https://www.spoj.com/problems/COT/en/
spoj.com
SPOJ.com - Problem COT
...
источник
17:31пожаловаться#5

K

Kotomord_λapki in pro.algorithms
круть какая...
источник
17:38пожаловаться#6

K

Kotomord_λapki in pro.algorithms
@aragaer  тут твоя помощь нужна, у меня что-то системы n*sqrt(n)* log(n) придумывается...
источник
17:53пожаловаться#7

A

Aragaer in pro.algorithms
по-моему поиск пути в глубину займет n, но при этом можно сразу поддерживать отсортированный список весов. Получается n*log(n), нет?
источник
18:06пожаловаться#8

A

Aragaer in pro.algorithms
ну или точнее не отсортированный список, а скорее "претендент на текущую k-ю позицию"
источник
18:07пожаловаться#9

DN

Dan Nesterov in pro.algorithms
Переслано от Dan Nesterov
Можно выписать эйлеров обход, на нем запустить МО по запросам, добавлять значения в вершине или убавлять в отдельную корневую декомпозицию. С помощью этой второй декомпозиции можно за О(1) прибавить в точке, за корень найти порядковую статистику.
источник
18:07пожаловаться#10

DN

Dan Nesterov in pro.algorithms
Переслано от Dan Nesterov
O(sqrt(n)*n) получается
источник
18:07пожаловаться#11

A

Aragaer in pro.algorithms
а, тогда это константа даже
источник
18:07пожаловаться#12

A

Aragaer in pro.algorithms
.. нет, не константа 8(
источник
18:07пожаловаться#13

K

Kotomord_λapki in pro.algorithms
Aragaer
по-моему поиск пути в глубину займет n, но при этом можно сразу поддерживать отсортированный список весов. Получается n*log(n), нет?
да, но от каждой вершины не хочется
источник
18:08пожаловаться#14

K

Kotomord_λapki in pro.algorithms
запросов тоже много
источник
18:08пожаловаться#15

K

Kotomord_λapki in pro.algorithms
Dan Nesterov
Переслано от Dan Nesterov
Можно выписать эйлеров обход, на нем запустить МО по запросам, добавлять значения в вершине или убавлять в отдельную корневую декомпозицию. С помощью этой второй декомпозиции можно за О(1) прибавить в точке, за корень найти порядковую статистику.
МО?
источник
18:11пожаловаться#16

DN

Dan Nesterov in pro.algorithms
Алгоритм МО
источник
18:12пожаловаться#17

K

Kotomord_λapki in pro.algorithms
Я бы писал нечто в таком стиле
Подвешиваем дерево за корень
Находим поддерево размера sqrt(N)
Отфильтровываем запросы, где одна из вершин в поддереве и где обе в поддереве
вторую группу можно пробрутить,
первая - подготовка для каждой вершины из поддерева отсортированного массива "путь до корня поддерева" и один dfs из корня наружу с поддержанием списка в сбалансированном дереве
Шаг n log n, шагов sqrt(n)
источник
18:15пожаловаться#18

K

Kotomord_λapki in pro.algorithms
но хрен знает, уложится ли это в TL
источник
18:16пожаловаться#19

A

Aragaer in pro.algorithms
ну кстати я бы тут отчаянно мемоизировал все возможные пути
источник
18:19пожаловаться#20