ПК
не учитывая D второго тура региона
Size: a a a
2020 March 10
DK
Сейчас скину крутую задачу
SF
не учитывая D второго тура региона
Какого года?
ПК
Какого года?
этого
DK
есть какие-нибудь хорошие задачи на ДП по (под)маскам?
DK
Еще Кефа и обеды (гуглится по названию), Kefa and dishes вроде на cf
DK
И с образовательного раунда, конечно же, турнир ситхов
https://codeforces.com/problemset/problem/678/E
https://codeforces.com/problemset/problem/678/E
ПК
как говорится, циановый — цвет надежды
DK
есть какие-нибудь хорошие задачи на ДП по (под)маскам?
Еще в atcoder educational dynamic programming contest (тоже гуглится) одна задача была где-то в середине
2020 March 11
АГ
Здравствуйте, не подскажете, можно ли в боре, построенном на обратном битовом представлении числа быстро искать mex? Я умею делать это за лог квадрат в декартовом дереве, но такой подход не работает в боре. Заранее спасибо.
KK
Можно и на прямом
KK
Только тебе эту штуку нужно поддерживать аккуратно
KK
Там чекать нужно существование левой/правой вершины при добавлении
DK
Можно и на прямом
Ему, видимо, нужен именно обратный
DK
На обратном без понятия как, на прямом делается за кол-во битов в числе элементарно
DK
Типо вот мы в корне и у нас старший бит определяется сейчас, осталось сформировать k битов, если в левом поддереве меньше чем 2^k листьев, то ответ там, иначе в правом
A
Если обратный код это реверснуть все биты числа, то там все идентично
A
А если это реверснуть маску числа как строку, то я хз
АГ
Типо вот мы в корне и у нас старший бит определяется сейчас, осталось сформировать k битов, если в левом поддереве меньше чем 2^k листьев, то ответ там, иначе в правом
А откуда мы возьмём число k?
DK
А откуда мы возьмём число k?
Обычно мы его знаем наперед, k=31 для инта, например, 63 для uint64_t