CD
А в группе левый потомок ДО по корню и правому считается
Size: a a a
2020 July 15
CD
хотя мб я не помню входные, давно этот момент разбирал
KK
Ну, отсечь до от фенвика по памяти можно, думаю.
Ну в сложных задачах, справедливости ради, сложно отсечь до от фенвика и не схватить какую-ибудь фигню, что чувак лишний раз скопировал массив и получил мл)
KK
По времени проще
DK
@webreh как-то сказал, что Фенвик это ДО без одной ветви. Типо если ты хранишь сумму в узле, то знать сумму в левом и правом поддеревьях - избыточно, так как sumRoot = sumLeft + sumRight
CD
да, это было в 14;14 примерно)
mq
Причем одно - красный, другое - нутелла
а зачем ты так отдельно выделил красных или нутелл?
до написанное желтым отличается от до написанного нутеллой чем то принципиально?
до написанное желтым отличается от до написанного нутеллой чем то принципиально?
DK
а зачем ты так отдельно выделил красных или нутелл?
до написанное желтым отличается от до написанного нутеллой чем то принципиально?
до написанное желтым отличается от до написанного нутеллой чем то принципиально?
ну tourist нумерует узлы в порядке эйлерова обхода, а желтый нумерует узлы 2*v+1, 2*v+2, кто-то копирует персистентное ДО на всякий случай чтобы стрелять из написанной и отдебаганной пушки по воробьям, кто-то пишет ленивое или неявное, или на указателях. Все ДО разные
KK
ну tourist нумерует узлы в порядке эйлерова обхода, а желтый нумерует узлы 2*v+1, 2*v+2, кто-то копирует персистентное ДО на всякий случай чтобы стрелять из написанной и отдебаганной пушки по воробьям, кто-то пишет ленивое или неявное, или на указателях. Все ДО разные
2*v и 2 * v + 1 же
KK
а зачем ты так отдельно выделил красных или нутелл?
до написанное желтым отличается от до написанного нутеллой чем то принципиально?
до написанное желтым отличается от до написанного нутеллой чем то принципиально?
Во-первых, как дима и написал, нутеллы юзают как раз эйлерову версию до (до бабочки вроде называется), да и там сильно эффективнее код получается
KK
И дело там не только в до в той задаче
DK
И дело там не только в до в той задаче
у меня проседает только формирование списка ивентов, то есть, произвольный доступ RAM 2 * n * log(1e9) раз
KK
у меня проседает только формирование списка ивентов, то есть, произвольный доступ RAM 2 * n * log(1e9) раз
Ну вон топовое решение работает за 300 мс, мое 1.5с
KK
(Найдите разницу)
DK
Ну вон топовое решение работает за 300 мс, мое 1.5с
то есть n*log(1e9) на ивентах работает медленнее чем n * log(1e9) * log(n) от фенвика
KK
то есть n*log(1e9) на ивентах работает медленнее чем n * log(1e9) * log(n) от фенвика
А там также log^2)
KK
Эта задача не решается за nlog
KK
Просто тупо потому что код эффективнее написан
DK
А там также log^2)
смотри, мое решение состоит из двух частей:
1. формирование списка событий
2. обработка списка событий
первая часть имеет асимптотику O(n log(n)), вторая O(n log(n)^2)
Вторая работает быстрее первой в два-три раза
1. формирование списка событий
2. обработка списка событий
первая часть имеет асимптотику O(n log(n)), вторая O(n log(n)^2)
Вторая работает быстрее первой в два-три раза
KK
смотри, мое решение состоит из двух частей:
1. формирование списка событий
2. обработка списка событий
первая часть имеет асимптотику O(n log(n)), вторая O(n log(n)^2)
Вторая работает быстрее первой в два-три раза
1. формирование списка событий
2. обработка списка событий
первая часть имеет асимптотику O(n log(n)), вторая O(n log(n)^2)
Вторая работает быстрее первой в два-три раза
Да