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

групп:

каналов:

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

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

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

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

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

go.backupland.com

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

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

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

Size: a a a

pro.algorithms

1930 membersпожаловаться на группу
2021 April 20

K

Kotomord_λapki in pro.algorithms
Вопрос к профи. Вроде простая задачка - дан массив из нулей и единиц, поддержать две операции - инвертировать интервал и найти количество единиц в интервале.
Быстрее чем парой декартовых деревьев это делается?
источник
22:43пожаловаться#1

K

Kotomord_λapki in pro.algorithms
Явно быстрее чем за логарифм обе операции нельзя
источник
22:44пожаловаться#2

K

Kotomord_λapki in pro.algorithms
Но константа важна
источник
22:44пожаловаться#3

p

ptr in pro.algorithms
Дерево отрезков быстрее будет
источник
22:49пожаловаться#4

K

Kotomord_λapki in pro.algorithms
Не придумал, как его тут настроить
источник
22:50пожаловаться#5

p

ptr in pro.algorithms
sum[v] - Количество единиц. ps[v] - 1/0 - инвертирован или нет.
источник
22:50пожаловаться#6

p

ptr in pro.algorithms
Обновлять как ((r - l) - sum[v])
источник
22:51пожаловаться#7

K

Kotomord_λapki in pro.algorithms
Примерно понял, можно попробовать
источник
22:57пожаловаться#8

K

Kotomord_λapki in pro.algorithms
А то с парой дд в лимит не укладывается
источник
22:57пожаловаться#9

K

Kotomord_λapki in pro.algorithms
Хоть на плюса переписывай
источник
22:57пожаловаться#10

K

Kotomord_λapki in pro.algorithms
О, понял, как дерево отрезков тут прикрутить
источник
23:00пожаловаться#11

CD

Constantine Drozdov in pro.algorithms
да пихай корневую, сотка зайдёт
источник
23:01пожаловаться#12

K

Kotomord_λapki in pro.algorithms
Но  интересно, можно ли декартовы разогнать
источник
23:01пожаловаться#13

K

Kotomord_λapki in pro.algorithms
Не, там ещё один множитель сверху
источник
23:02пожаловаться#14

K

Kotomord_λapki in pro.algorithms
Первое, что подумал
источник
23:02пожаловаться#15

A

AntiSpamBot in pro.algorithms
This is spam protection. You have 30 seconds to press the button or you will be banned!
источник
23:57пожаловаться#16
2021 April 21

CD

Constantine Drozdov in pro.algorithms
слушайте, а почему дерамида с рандомным мерджем
https://habr.com/ru/post/240519/
не вырождается рано или поздно в цепочку?
скажем, при повторении операции "взять середину, удвоить, повторить"
Хабр
Персистентное декартово дерево по неявному ключу
Осторожно, персистентность Сегодня достаточно необычный день, не правда ли? Как часто на Хабре появляются статьи про персистентные структуры данных? И именно сег...
источник
01:37пожаловаться#17

K

Kotomord_λapki in pro.algorithms
попробовал порандомить на 100000,  больше 50 не нашлось
источник
01:42пожаловаться#18

K

Kotomord_λapki in pro.algorithms
могу код скинуть, тащемта
источник
01:42пожаловаться#19

NK

Nikolai Karpov in pro.algorithms
Что значит с рандомным мерджем ?
источник
01:43пожаловаться#20