A
Ну, как по мне самое простое это персистентное ДО
Size: a a a
2020 March 04
A
Оно имхо несложное и почти как обычное на указателях
f
+ можно и без них
K
Знаю решение с до (правда, не персистентным
A
Какое?
K
шаг 1 - дерево отрезков, во всех нелистьях - 0, в листьях - 1
шаг 2 - в ближайший общий предок двух листьев с одинаковым значением вписываем -1
шаг 3 - перестраиваем до так, что в каждом узле - сумма в поддереве
шаг 2 - в ближайший общий предок двух листьев с одинаковым значением вписываем -1
шаг 3 - перестраиваем до так, что в каждом узле - сумма в поддереве
K
и теперь просто считаем сумму
K
на шаге 2 накапливаем, само собой
A
интересно
p
Можно фенвиком в оффлайне
DK
Как решить корневой декомпозицией задачу о различных числах на отрезке?
Запросы на изменение есть?
DK
Хм, Окей
Ну мне кажется мо какое то сложное и излишнее для этой задачи
Ну мне кажется мо какое то сложное и излишнее для этой задачи
Алгоритмом МО получается чистые O(n sqrt(n))
Я на educational контесте на codeforces эту штуку алгоритмом Мо сдавал, быстро пишется и быстро сдается
Строчек там меньше, чем у персистентного до
Я на educational контесте на codeforces эту штуку алгоритмом Мо сдавал, быстро пишется и быстро сдается
Строчек там меньше, чем у персистентного до
A
Я затупил, видимо, насчет персистентого ДО, поскольку можно то же самое обычным сделать в оффлайне
A
Ну или фенвиком, как тут предложили
f
Запросы на изменение есть?
Все в оффлайне
f
Блин, а где про мо почитать?)
DK
Все в оффлайне
Там простая идея:
Запомнить запросы Query{left, right, id}
Распределить их по блокам размера sqrt(n) по левой границе, внутри блоков посортить по правой: если блок с четным индексом, то в порядке возрастания правой границы, иначе в порядке убывания
Дальше методом двух указателей обработать все запросы
Запомнить запросы Query{left, right, id}
Распределить их по блокам размера sqrt(n) по левой границе, внутри блоков посортить по правой: если блок с четным индексом, то в порядке возрастания правой границы, иначе в порядке убывания
Дальше методом двух указателей обработать все запросы
f
А можно ли как то это сделать просто корневой? Просто я пытался, но не получается
DK
А можно ли как то это сделать просто корневой? Просто я пытался, но не получается
Можно, но выйдет сложнее и больше кодить