Здравствуйте. Наверное, многие из вас, читая статью о декартовых деревьях на сайте emaxx, увидели описание "магической" операции union() — объединение двух декартовых деревьев. Там указано, что ее ассимптотика составляет O(Mlog(N / M)). Вопрос заключается в следующем: какую величину имеет константа M и откуда взялась такая ассимптотика операции?

Здравствуйте. Хотел бы узнать решение следующей задачи. Дан массив a[0..N-1]. Нужно отвечать на запросы двух типов, желательно за O(log^2(N)) на запрос: 1) L R x — найти кол-во различных элементов отрезка массива a[L..R], меньше либо равных x. 2) i x — изменить элемент a[i] на x. Знаю, как находить кол-во различных элементов на отрезке за O(log^2(N)) на запрос. Думал над применением похожей идеи в данной задаче, но ничего нормального так и не придумал. Какие будут идеи?

Здравствуйте, пользователи Codeforces. Решаю задачу 1051F. Мое решение упорно MLится на 11 тесте, хотя по моим подсчетам ML быть не должно. В чем дело? UPD. Тема закрыта, ошибка найдена.

Приветствую всех. Хотел бы узнать, как решить одну задачу (уже не помню откуда). Дан неориентированный 0-1 граф с n вершинами и m ребрами и число k. Необходимо найти остовное дерево с суммарным весом ровно k (или сообщить, что такого не существует). Ограничения: 1 <= n, k <= 10^5, 1 <= m <= 2 * 10^5. Время 2 сек, память 256 Мб. У кого какие идеи?

Приветствую всех пользователей Codeforces. Возникла задача разделить один большой многочлен на другой. Решил использовать БПФ, но если при умножении многочленов все более-менее понятно, а именно перемножаются соответствующие значения ДПФ двух многочленов, то при делении возникают сложности, ведь значения ДПФ могут быть равны 0, а на 0 поделить, увы, не получится. Что же делать в такой ситуации? Буду также рад, если вы предложите какую-нибудь статью, которая разрешит мой вопрос (желательно на русском).