Спасибо @serkan за то, что он заметил, что все таки mex с изменениями все таки можно искать на отрезке за O(n log^2 n). Эта задача есть здесь: olympiads.ru/zaoch/2018-19/zaoch/quallong.zip с решением. Называется mex-unkeked.
честно очень хочется чтобы ты еще записывал видео про задачи типа дп на деревьях или дп на графах чтото в таком роде, так как новичкам как по мне именно похожие темы труднее всего даются, (мне например) буду заранее благодарен
@@peltorator Идея примерно такая: давай для каждого числа посмотрим, на каких отрезках его нет. Если число входит на позициях a1, a2, ..., ak, то его нет на подотрезках отрезков [1; a1) (a1, a2), ... (ak; n]. Тогда, по сути, у нас есть множество отрезков с числами и надо говорить минимальное число среди отрезков, которые нас накрывают. Давай построим дерево отрезков на правых позициях и в каждой вершине будем хранить какое-нибудь дерево, у которого ключ - это множество левых значений, а значение - это число на отрезке. Тогда добавить отрезок [l, r] со значением x - это запушить на отрезке [l, r] в деревья пару (l, x), а ответить на запрос - во всех деревьях на пути от r до корня взять минимум в деревьях по значениям для ключей >= l и взять минимум этих минимумов. Тут именно важно, что мы не пушим пару (l, x) ниже в поддеревья (ибо это невозможно по-нормальному сделать), а просто оставляем ее в вершинах, ответственных за отрезок, это позволяет просто брать минимум на пути от корня до вершин, ответственных за отрезок. Реализация авторского заочки: pastebin.com/eY6N3yzb В условии заочки еще можно заметить что там есть ограничение сильное ограничение на количество изменений, но запросов get может быть много. Это было сделано не случайно - изменить элемент достаточно дорого, ибо это много запросов к ДО, а вот сделать get дёшево (всего один запрос к ДО).
Недавно, кст, решал задачку на литкоде, была очень похожая, нужно было найти в последовательности [1;n] пропущенные элементы. Могут быть дубликаты. Так вот, я захерачил какой-то in_place за линию по времени)
Спасибо @serkan за то, что он заметил, что все таки mex с изменениями все таки можно искать на отрезке за O(n log^2 n). Эта задача есть здесь: olympiads.ru/zaoch/2018-19/zaoch/quallong.zip с решением. Называется mex-unkeked.
Искал медь, нашел золото! Автор потрясающе излагает алгосы, так еще и контесты по ним составляет. Жаль только, что давно канал забросил
Снова очень классное видео, спасибо!!
Спасибо!
Как обычно, спасибо большое за крутое пояснение
честно очень хочется чтобы ты еще записывал видео про задачи типа дп на деревьях или дп на графах чтото в таком роде, так как новичкам как по мне именно похожие темы труднее всего даются, (мне например) буду заранее благодарен
Там есть решение за O(n*log^2) для меняющегося массива в архиве длинного тура открытки 2летней давности.
Ого. Можно ссылочку?
@@peltorator
Идея примерно такая: давай для каждого числа посмотрим, на каких отрезках его нет.
Если число входит на позициях a1, a2, ..., ak, то его нет на подотрезках отрезков [1; a1) (a1, a2), ... (ak; n]. Тогда, по сути, у нас есть множество отрезков с числами и надо говорить минимальное число среди отрезков, которые нас накрывают.
Давай построим дерево отрезков на правых позициях и в каждой вершине будем хранить какое-нибудь дерево, у которого ключ - это множество левых значений, а значение - это число на отрезке. Тогда добавить отрезок [l, r] со значением x - это запушить на отрезке [l, r] в деревья пару (l, x), а ответить на запрос - во всех деревьях на пути от r до корня взять минимум в деревьях по значениям для ключей >= l и взять минимум этих минимумов.
Тут именно важно, что мы не пушим пару (l, x) ниже в поддеревья (ибо это невозможно по-нормальному сделать), а просто оставляем ее в вершинах, ответственных за отрезок, это позволяет просто брать минимум на пути от корня до вершин, ответственных за отрезок.
Реализация авторского заочки: pastebin.com/eY6N3yzb
В условии заочки еще можно заметить что там есть ограничение сильное ограничение на количество изменений, но запросов get может быть много.
Это было сделано не случайно - изменить элемент достаточно дорого, ибо это много запросов к ДО, а вот сделать get дёшево (всего один запрос к ДО).
@@chegoryu О, спасибо за подробное объяснение! Ну реализацию я уже скинул в закрепленном комментарии.
Недавно, кст, решал задачку на литкоде, была очень похожая, нужно было найти в последовательности [1;n] пропущенные элементы. Могут быть дубликаты. Так вот, я захерачил какой-то in_place за линию по времени)
Ещё на algorithmica.org круто написано про дерево отрезков
А чё я то?
Ребят, что это я сейчас посмотрел ??