Привет, Codeforces!
Вчера закончился длинный тур Открытой олимпиады этого года, который проходил с 21.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.
Я постараюсь описать свои мысли в ходе решения как можно подробнее, но я не гарантирую, что начинающим спортпрогерам всё будет понятно ;)
Собственно, ниже мои решения + реализации (прощу прощения, если код трудночитаем):
Заметим тот факт, что для любого $$$1 < i \le n$$$ будет выполняться $$$max(p_{0:i}) \ge i$$$. Назовём хорошей позицией такое $$$i$$$, что $$$max(p_{0:i}) = i$$$.
Понятно, что если закончить очередной подотрезок не на хорошей позиции, то само число $$$i$$$ не войдет в этот подотрезок -> оно точно встретится в результирующей перестановке позже $$$max(p_{0:i})$$$, противоречие. То есть, концы отрезков могут совпадать только с хорошими позициями -> перестановку можно разбить на $$$k$$$ отрезков с необходимым свойством только тогда, когда количество хороших позиций в этой перестановке $$$\ge k$$$. Построение ответа достаточно тривиально — сделаем концами отрезков $$$k$$$ последних хороших позиций.
Асимптотика: $$$O(n)$$$.
Условие задачи можно переформулировать так — найти количество чисел $$$\le a_i$$$, таких, что сумма двух соседних цифр в их записи не превышает $$$10$$$. К этому можно придти кукареком (перебирая первые числа и находя закономерности) или через математику.
В любом случае, переформулированную задачу можно решать с помощью ДП по цифрам, а именно по первой половине записи числа (потому что вторая половина будет зеркальна первой). Состоянием будет последняя рассмотренная позиция и цифра, которую на неё записали.
Асимптотика: $$$O(log_{10}(a_i))$$$ для одного запроса.
В решениях ниже я буду считать, что $$$n = m$$$, поскольку в максимальных тестах это действительно так.
Разобьём решение на 4 части: для групп 1-2, для группы 3, для группы 4 и для групп 4-5.
Группы 1-2: запустим алгоритм Дейкстры на графе. На каждой итерации переберём ребро, исходящее из вершины, и если у него есть продолжение, то прорелаксируем все рёбра, достижимые из текущего по продолжениям. Иначе, релаксируем только рассмотренное ребро.
Асимптотика: вроде бы $$$O(n^2 log n)$$$, но я не умею строго пруфать это.
Группа 3: то же решение, что и для групп 1-2, но поскольку в этой группе рёбра не имеют продолжений, прийти к этому решению гораздо проще + асимптотика лучше.
Асимптотика: $$$O(m log n)$$$.
Группа 4: в этой группе можно написать 0-1 BFS (поскольку все ребра будут иметь вес либо 0, либо 1) или решение для группы 5.
Асимптотика решения с 0-1 BFS: $$$O(n + m)$$$.
Группа 5: представим, что вместо каждого ребра $$$v$$$ у нас есть $$$max(w) + 1$$$ его копий с весами от $$$0$$$ до $$$max(w)$$$. В таком случае, если приходим в $$$v$$$ из копии ребра $$$u$$$ с весом $$$x$$$, то:
$$$v$$$ является продолжением $$$u$$$ -> обновим ответ для копии $$$v$$$ с весом $$$max(0, x — 1)$$$
$$$v$$$ не является продолжением $$$u$$$ -> обновим ответ для копии $$$v$$$ с весом $$$w_v$$$
Можем и здесь запустить Дейкстру, но нужно сделать важную оптимизацию, не перебирая те ребра, которые точно не можем прорелаксировать. А именно, если находясь в ребре $$$v$$$, мы не можем прорелаксировать хотя бы одно ребро, в которое можно придти из $$$v$$$ и которое не его продолжение, то мы аналогично не сможем прорелаксировать другие не-продолжения ребра $$$v$$$.
Асимптотика: $$$O(m * max(w) * log(m))$$$.
В этой задаче существует масса вариаций с решениями на сетах, но я рассмотрю не совсем обычное, но более простое для меня решение с использованием техники Segment Tree Beats.
Будем считать, что какая-то позиция обновлена в момент времени $$$x$$$, если после $$$x$$$-ой операции на ней появился снег, до $$$x$$$-ой операции на ней не было снега, и если этот снег не убрали до текущей операции. Если на позиции сейчас нет снега, то можно считать, что эта позиция была обновлена в момент $$$INF$$$.
Будем хранить дерево отрезков с тремя параметрами для каждой вершины: min_prev_time, max_prev_time и total_time, где min_prev_time — минимальный момент времени, в который обновили какую-то позицию на отрезке; max_prev_time — аналогично предыдущему, но на максимум; total_time — сумма всех total_time на этом отрезке.
Если операция в момент времени $$$t$$$ имеет тип +, делаем min= $$$t$$$ для всех позиций с $$$l$$$ по $$$r$$$.
Если операция в момент времени $$$t$$$ имеет тип -, делаем total_time += $$$t$$$ — prev_time и prev_time = $$$INF$$$ для всех позиций с $$$l$$$ по $$$r$$$.
Теперь определимся, какие-же tag/break условия нужно взять. Понятно, что делать min= $$$x$$$ на отрезке, на котором максимум меньше $$$x$$$, не имеет смысла, поэтому break-condition для операции +: max_prev_time < $$$x$$$. Аналогично, tag-condition: min_prev_time > $$$x$$$.
Break-condition для операции -: min_prev_time == $$$INF$$$, tag-condition: min_prev_time == max_prev_time.
Строгого доказательства времени работы не будет, потому что не силён в методе потенциалов :( Буду очень рад, если кто-то в комментариях найдёт асимптотику данного решения.
В этой задаче можно сделать корневую декомпозицию с идеей разбиения объектов по тяжести.
Скажем, что число $$$x$$$ является тяжелым, если оно встречается $$$\ge k$$$ раз в массиве. Отсюда понятно, что тяжёлых чисел не больше $$$n / k$$$.
Предподсчитаем ответ для всех различных пар чисел в массиве, в которых есть хотя бы одно тяжелое число. Понятно, что таких пар будет не больше $$$n * (n / k)$$$. Это можно сделать одним проходом по массиву, храня для каждого тяжелого числа количество уже рассмотренных его копий. Асимптотика: $$$O(n * (n / k))$$$.
После предподсчета начнем обрабатывать запросы. Если в текущем запросе нет ни одного тяжелого числа, можно найти ответ методом указателей за $$$O(k)$$$. Иначе, мы уже посчитали ответ в предподсчете.
Таким образом, получаем сложность решения $$$O(n * (n / k) + q * k)$$$. Если предположить, что $$$n = q$$$, то выгоднее всего будет взять $$$k = \sqrt{n}$$$, получим $$$O((n + q) * sqrt(n))$$$.
Первые 4 группы достаточно легко сдаются склейкой различных простых идей, мы же приступим сразу к 5 группе.
Есть один интересный способ проверки на то, является ли отрезок статической строки ПСП. А именно, если посчитать стеки для всех префиксов строки, то $$$[l; r]$$$ будет являться ПСП тогда и только тогда, когда стеки для префиксов $$$[0; l - 1]$$$ и $$$[0; r]$$$ равны. Разумеется, сравнивать стеки поэлементно очень долго, поэтому захешируем их.
Получаем решение для 5 группы, которое работает за $$$O(n + q)$$$.
В 6 группе всё уже не так просто, поскольку появляются изменения в точке. Если мы хотим и дальше использовать хеширование в решении, то полиномальное нам точно не подойдет, поскольку наше хеширование должно быть ассоциативным (чтобы не считать хеш поэлементно) и некоммутативно (чтобы порядок элементов имел значение). Вспоминаем, что умножение матриц выполняет оба этих свойства!
Значит, можно каждой открытой скобке сопоставить матрицу 2x2 из случайных чисел от $$$0$$$ до $$$MOD - 1$$$, а каждой закрытой скобке — матрицу, обратную матрице открытой скобки такого же типа. В таком случае, если подотрезок является ПСП, то произведение матриц на нём является единичной матрицей.
Чтобы добавить обновления в точке, построим дерево отрезков с операцией умножения матриц, обновление в таком случае делается тривиально.
Взломать такой хеш гораздо труднее, чем полиномиальный хеш, поэтому матрицы 2x2 будет достаточно.
Итоговая асимптотика: $$$O(d^3 * n * log(n))$$$, где $$$d$$$ — выбранный размер матрицы для хеширования.
Определим ПСП немного иначе: ПСП называется такая строка, что для любого $$$0 \le i < n$$$ на суффиксе $$$[i:n]$$$ находится ровно $$$(n - i) / 2$$$ открытых скобок (поскольку при большем или меньшем количестве не будет подходящего баланса).
Из этого определения гораздо легче вывести жадное решение задачи.
Будем рассматривать все позиции по уменьшению их стоимости и параллельно для каждой позиции хранить количество открытых скобок, которое мы можем поставить на суффиксе этой позиции. Если текущая позиция — p и на префиксе $$$[0:p + 1]$$$ мы в любую позицию ещё можем поставить одну открытую скобку, сделаем это и обновим количества на префиксе. Если же не можем сделать, то переходим к следующей позиции.
Для поддерживания количеств открытых скобок, которые можем поставить на суффиксе, удобнее всего использовать дерево отрезков на массовые операции. Получаем решение с асимптотикой $$$O(n log n)$$$.
Получившееся решение отдалённо напоминает алгоритм построение миностова. Однако, я не умею строго доказывать корректность этого алгоритма, то есть это кукарек (впрочем, как и в большинстве жадных решений ;)).
Переформулируем задачу в более формальный вид. Обозначим за $$$f(l, r)$$$ ответ для отрезка $$$[l; r]$$$. В таком случае, если $$$a_l \ne a_r$$$, нетрудно доказать, что $$$f(l, r) = max(f(l + 1, r) + 1, a_r - a_l)$$$ (случай $$$a_l == a_r$$$ тривиален).
Эту же формулу можно представить немного в другом виде. Для каждого $$$p$$$ в массиве $$$nx$$$ будем хранить самую правую позицию массива, число на которой равно $$$a_p$$$. Пусть $$$x = nx_l$$$, $$$s = (a_r - a_l) + (nx_l - l)$$$. Пока $$$a_x \ne a_r$$$, будем "прыгать" через блок равных элементов ($$$x = nx_{x + 1}$$$), изменяя текущий баланс (прибавляя разницу между новым и старым значением, вычитая длину блока). В те моменты, когда баланс будет меньше $$$0$$$, будем вычитать его из $$$s$$$ и делать снова равным $$$0$$$. Доказательство корректности перехода от $$$f(l, r)$$$ к этому алгоритму я оставляю читателю.
Итак, у нас уже есть достаточно быстрый алгоритм, который получает 76 баллов. Чтобы получить полный балл, можно заметить, что можно построить прыжки через прыжки через блоки равных чисел. А именно, из каждого момента, в котором у нас нулевой баланс, мы будем прыгать в ближайший момент с отрицательным балансом, обновляя ответ и снова приходя в момент с нулевым балансом.
Однако и этого мало, потому что у нас может быть очень много таких моментов. Поэтому, на новых прыжках мы построим бинапы на сумму, а чтобы построить их, пройдемся по блокам равных элементов с деревом отрезков.
Получившееся решение работает за $$$O((n + q) log n)$$$.
Пусть pr — массив простых чисел, где $$$pr_0 = 2, pr_1 = 3$$$ etc.
Нам нужно найти $$$f(n, b)$$$, где $$$f(x, y) = x$$$ при $$$x < pr_y$$$. Функцию можно вычислять по следующей формуле: $$$f(n, b) = f(n, b - 1) + f(n / pr_b, b - 1) + ... + f(n / (pr_{b}^k), b - 1)$$$, где $$$k = floor(log_{pr_b}(n))$$$.
Далее можно заметить, что значения $$$f(n, b)$$$ при достаточно маленьких ($$$\le 2000000$$$) $$$n$$$ будут использоваться очень часто, поэтому эти значения можно запомнить в массиве и не пересчитывать много раз. Помимо этого, для $$$b \le 8$$$ (или 9) будет не так много различных чисел, которые в разложении содержат множители не больше $$$pr_b$$$ (а именно, порядка пары десятков миллионов), а значит, все эти числа можно также сохранить в отсортированном массиве и при маленьких b вместо запуска функции находить ответ lower_bound-ом к этому массиву).
Совокупность этих идей при аккуратной реализации даёт 82 балла.
Идеи на 100: заметим, что $$$f(n, b) = f(n, b - 1) + f(n / pr_b, b)$$$ (это очевидно вытекает из прошлой формулы), то есть, можно вычислять значения функции не в глубину, а в ширину. Если прикрутить различные оптимизации к стандартному алгоритму BFS, получится решение, которое на максимальном тесте работает около 3.6 секунд, чего достаточно для получения 100 баллов.
Идеями на 100 со мной поделился grishared, за что я ему крайне признателен.
Спасибо за внимание!
Автокомментарий: текст был обновлен пользователем tiom4eg (предыдущая версия, новая версия, сравнить).
Жесть, крут)
В C на 47 заходил квадратик от входящих на выходящие))))
Dшка, более лёгкая идея: Делаем сет отрезков, обрабатываем слева направо запросы. Если передвигаемся из I в I + 1, удаляем все отрезки с r = I, добавляем все с l = I + 1 Реализация глинистая(
C:пишем BFS: (расскажу решение для цепочек и циклов, для деревьев обобщается) рассмотрим для какой-то цепочки первую вершину (пусть v), которую мы на ней отметим (и будем на каждой цепочке поддерживать все линейные функции, через которые будем пересчитываться) тогда заметим, что если мы обновим кратчайшие расстояния через вершинку v, то оптимальной будет вершинка, наиболее близкая к ней: пересчитаем эту вершинку через линейные функции, принадлежащие цепочке, и добавим ее в priority_queue пересчитваем и добавляем на отрезках с помощью ДО + Li-Chao (не писал, было очень лень, мб не работает)
В C есть только одна нетривиальная конструкция — это цикл (возможно, вырожденный), в каждую вершину которого приходит несколько (возможно, ноль) деревьев. Чтобы побороть цикл, можно мысленно разрезать по ребру и удвоить его, в одной половине учитывая все подвешенные деревья, а в другой — нет. Ну и дальше действительно делаем ДО/HLD + Ли-чао.
Это должно работать, потому что нам не нужно ходить по циклу больше одного раза, ну и полученная конструкция также будет деревом :)
HLD + Li-Chao будет $$$n \log^3n$$$ при $$$n \leq 500 000$$$?
Ну если строить Li-Chao на каждом из тяжелых путей, то должно быть $$$O(n log^2 n)$$$, Qwerty1232 вроде бы знает какой-то хак, чтобы получить $$$O(n log n)$$$. Лог в кубе, конечно, не должен заходить.
Как сделать $$$O(n\log^2n)$$$ с Li-Chao?
В моей реализации подход HLD + Li-Chao был $$$O(n \log^3n)$$$ с малой константой, потому что вставлять линейные функции нужно не на всём Li-Chao, а на суффиксе, и Li-Chao вроде бы это умеет делать только за $$$O(\log^2 n)$$$. При релаксации по ребру нам нужно добавить прямую в $$$O(\log n)$$$ тяжелых путей.
Я знаю решения за:
Второе уже выглядело впихуемо, возможно даже первое, если не заставлять Li-Chao поддерживать минимум.
Для G у меня было решение попроще в плане написания и понятности.
Скажем, что изначально ответ — это строка вида $$$()()()...()()$$$. Затем, заметим полезный факт — если есть закрывающая скобка с индексом $$$i$$$, то её можно заменить на открытую скобку с индексом $$$j > i$$$ и ПСП останется ПСП. Теперь будем идти по строке справа налево и применять следующий жадный алгоритм: поддерживаем сет из открытых скобок (их стоимостей), если встретилась закрытая скобка — посмотрим на минимум в сете, если заменить его выгодно — заменяем. Итого получится оптимальная строка.
Также приведу код:
а будет дорешка?
Привет, дорешка появилась сегодня :)
https://codeforces.com/gym/104162
Для задачи H есть решение, которое можно оптимизировать для ответа на запрос за O(1).
https://pastebin.com/TPYea9hF
Задача C. Доставка еды
Общая идея -- Дейкстра + структура данных для обновления времен посещения перекрёстков по цепочке продолжений дорог.
Хотим построить структуру данных на цепочках дорог. Выделяем dfs-ом сток/терминальный цикл какой-то цепочки. От стока/каждой вершины цикла запускаем dfs по обратным рёбрам, бьём деревья на тяжелые пути, создаем деревьях Li-Chao на рёбрах каждого и на терминальном цикле.
В Дейкстре берем очередной ближайший перекрёсток, как обычно релаксируем достижимые вершины, релаксируем суффиксы деревьев Li-Chao, отвечающих за выходящие ребра, после релаксации каждого дерева релаксируем суффикс следующего с точки входа в него, обрабатываем терминальный цикл -- после релаксации полного Li-Chao продолжать ходить по кругу смысла нет.
При релаксации куска Li-Chao нужно возвращать Дейкстре текущую ближайшую непосещённую вершину, это можно делать внутри самого Li-Chao, поддерживая живой минимум на каждом подотрезке. При вставке прямой нужно находить первую живую точку на отрезке и релаксировать минимум, плюс отдельно обрабатывать горизонтальные участки "парабол" времени посещения, константа получается не очень.
Много операций тратится на поддержание минимума на подотрезках, хотя нас интересует только минимум на всём Li-Chao. Заметим, что операции, меняющие минимум, довольно просты. При добавлении прямой достаточно взять первую живую точку от её начала и до горизонтального участка параболы или любую точку с горизонтального участка параболы как потенциальный новый минимум. При удалении минимума достаточно рассмотреть точки, до которых мы не дошли из-за него, фактически это следующая живая точка за ним, по которой запросом в Li-Chao и сравнением с минимальным горизонтальным участком найдём время посещения.
От Li-Chao остаётся только базовая часть, хранение прямых, и добавляется DSU для поиска следующей живой точки.
В последней оптимизации мы накнулись на идею, что параболы, минимизируемые в такой-то живой точке, дальше ничего интересного не делают, пока соответствующий перекрёсток не будет рассмотрен в Дейкстре. Избавимся от хранения парабол на множестве точек, будем держать параболы в первой живой точке, на которую они действуют -- ребре, ведущем в нерассмотренный перекрёсток. Тогда, релаксируя в Дейкстре из некоторого перекрёстка, достаточно сделать классические релаксации без учета продолжений дорог и пропихнуть множества парабол из каждой входящей дороги в следующую дорогу по цепочке её продолжений, входящую в нерассмотренный перекрёсток. Следующую опять находим через DSU на рёбрах.
Храним параболы, участвующие в нижнем профиле, в std::set, обрабатываем вставку одной параболы и пропихивание множества парабол через приливание меньшего к большему, чтобы корректно обрабатывать разные точки отсчета сливаемых множеств храним вместе с множеством горизонтальный сдвиг всех парабол множества и сдвигаем явно каждую параболу меньшего множества, чтобы выравнять с большим.
При сливании множеств, если отношение их размеров $$$\frac ab$$$ меньше $$$\log n$$$, сольём за $$$O(a + b)$$$, иначе за $$$O(b \log a)$$$. Вроде бы это даёт упомяную асимптотику, но почти не меняет время работы, отчасти из-за кеширования пути в std::set вершины к корню и её соседям при последовательной вставке стандартным приливанием.
Edit: поправил асимптотику.
Указатели -- медленно, платить второй логарифм только из-за слияния множеств тоже неприятно. Как минимум можно заменить std::set на декартово дерево со слиянием за $$$O(b \log \frac ab)$$$.
Заметим, что нам не нужно искать значение выпуклой оболочки в произвольной точке, только в некотором "начале отсчета", который двигается вправо с каждым приливанием множеств. Это напоминает кучу -- нам не обязательно поддерживать коректный нижний профиль слева направо по дереву, достаточно поддерживать его сверху вниз, обрабатывать запросы вставки и удаления корня с сохранением корректности профиля на вертикальных путях. В таком случае можно показать, что пусть мы и храним лишние параболы, не участвующие в нижнем профиле полного множества, ничего не сломается. Алгоритм Shadow merge для бинарных куч вроде бы позволяет добиться желаемой асимптотики, но вставить в него поддержку инварианта -- "нижнепрофильность" вертикальных путей -- выглядит очень больно. Возможно, есть версия кинетической кучи на массиве, позволяющая делать ровно то что нужно, если кто-то знает -- поделитесь, пожалуйста.
Вместо классической бинарной кучи можно использовать более слабую структуру. Будем хранить множество прямых в виде набора отсортированных нижних профилей, размерами по степеням двойки. Сливаем два нижних профиля одного размера за линию от суммы размеров, апгрейдим результат то следующего ранга-степени двойки, выкидываем в процессе "перекрытые" прямые, выкидываем прямые, которые перестали быть интересны в текущем начале отсчета, выкидываем прямые, которые уперлись в свой конец -- горизонтальный участок параболы. Несложно показать что приливания и запросы сдвига начала отсчета работают суммарно за $$$O(n \log n)$$$.
Задача I. Гладкие числа
Обозначим ответ за $$$\Psi(n, b)$$$. Рассмотрим b-гладкие числа, у которых максимальный простой делитель равен $$$p \leq b$$$. Но их в точности $$$\Psi(n / p, p)$$$: взяв это простое число, мы можем набрать сколько угодно простых, не больших него, так, чтобы произведение было не больше $$$n$$$. Раскрывая по $$$p$$$, получаем Buchstab’s Identity: $$$\Psi(n, b) = 1 + \sum_{p \leq b}\Psi(n/p, p)$$$. Числа, которые мы посещаем при рекурсивной реализации -- частные $$$n$$$ и гладкого числа, имеющего делители от $$$p$$$ до $$$b$$$.
Можно провести некоторую границу, научиться отвечать для любого числа ниже неё, чему равно $$$\Psi(n, p)$$$, и обрезать рекурсию, как только мы эту границу пересекли. Но граница $$$n \leq C$$$ довольно посредственная: чем дальше по простым продвинулась рекурсивная часть, тем больше точек выше границы она рассматривает, аналогично для нижней части. Поэтому можно сделать границу более хитрой -- чем дальше продвигается по простым половина решения, тем больше от неё отсекается.
Для первого AC я предподсчитал $$$\Psi(n, p)$$$ для $$$n \leq 4e5$$$, а так же список гладких чисел до $$$n \lt 2^{32}, p_{min} \gt 47$$$, запросы из рекурсивной части либо выполняются сразу таблицей, либо захватываются списком гладких для дальнейшего выполнения, либо продолжают рекурсивный спуск. После этого список гладких чисел сортирует запросы и merge-like алгоритмом сопоставляет их с самим списком, насчитывая для каждого запроса ответ. Деление на простые как compile-time константы существенно ускоряет решение. Это работает за ~0.8s.
Далее я оптимизировал решение. Как было замечено, рекурсивный спуск очень похож на саму генерацию маленьких гладких чисел. Поэтому вместо рекурсии + сортировки можно хранить множество запросов, последовательно расширять его по новому простому, мержить куски для поддержания отсортированной последовательности, отсекать запросы, которые пересекли границу. Границу можно сделать ещё более хитрой: для каждого $$$p$$$ установить свою границу на $$$n$$$. Оптимальный профиль границы монотонный, но найти его по-нормальному, наверное, нельзя, не жертвуя эффективностью алгоритма. Но можно найти его любым оптимизационным алгоритмом, финальное решение работает за ~0.2s.
Статическое (на 76 баллов), но детерминированное решение F.
Определим p[i] := минимальная позиция j > i такая, что подстрока [i..j] сбалансирована. Эту величину можно посчитать одним проходом справа налево с помощью простой динамики. Теперь из каждого i проведём ребро в p[i] + 1. Получим лес.
Как отвечать на запрос [l; r]? Для этого нужно просто проверить, что вершина r + 1 является родителем вершины l. Это можно делать, предподсчитав бинапы или tin и tout для каждой вершины dfs'ом.
Приведу другое решение Dшки с Segment Tree Beats.
Для начала нужно понять, что ответ для позиции $$$i$$$ можно посчитать так:
присваиваем $$$ans[i]=m,$$$ идем по всем запросам по порядку $$$j=0, j \to m,$$$ если позиция $$$i$$$ входит в границы $$$j$$$-го запроса и если его тип не равен типу прошлого запроса, покрывающего позицию $$$i,$$$ то прибавляем такие величины: если $$$type[j] = ClearSnow,$$$ то $$$ans[i]$$$+= $$$m-j,$$$ иначе если $$$type[j] = AddSnow,$$$ то $$$ans[i]$$$-= $$$m-j.$$$
Теперь перенесем эту идею на дерево отрезков:
Мы можем делать такие операции для отрезка позиций, только если у каждой из них прошлый запрос был одинаковый, то есть если на каждой из них сейчас лежит снег, либо не лежит ни на одной.
Обозначим $$$CntSnow$$$ — количество покрытых снегом позиций на отрезке, $$$Len$$$ — длина отрезка. Будем спускаться по дереву, пока $$$CntSnow ≠ 0$$$ $$$or$$$ $$$CntSnow ≠ Len,$$$ далее можно обновить значения как нам нужно.
Доказательство асимптотики $$$O(mlogn)$$$:
Каждый запрос к ДО создает не больше $$$O(logn)$$$ вершин дерева со свойством $$$CntSnow ≠ 0$$$ $$$or$$$ $$$CntSnow ≠ Len,$$$ при этом запрос убирает это свойство для всех вершин, в которые спуск был совершён из-за расширенного $$$Tag$$$_$$$Condition.$$$ Таким образом мы можем совершить не больше $$$O(mlogn)$$$ дополнительных спусков за $$$m$$$ запросов.
Для задачи Е есть более просто решение(без корневой декомпозиции):
Для начала сожмем все числа.
Посчитаем массив pos[x] — массив позиций на которых встречается число x.
Теперь обрабатываем запросы и запоминаем ответ для каждой упорядоченной пары.
Запоминать ответ для пар можно при помощи такой структуры как std::map.
Отвечаем на запрос {x, y}:
1. У нас эта пара уже была посчитана. Тогда просто выводим ответ.
2. У нас эта пара не была посчитана. Тогда считаем ответ, причем перебираем позиции того числа, которое встречается реже(определить это можно при помощи массива pos). Запоминаем ответ.
Это решение у меня зашло на 100 баллов, но я не могу показать асимптотику алгоритма. Буду рад, если кто-нибудь подскажет.
Код решения: https://pastebin.com/hi5u3ntc
$$$O((m + n) \sqrt n \log n)$$$, примерно, ведь если размер маленькой меньше, чем $$$\sqrt n$$$, то мы отработаем за его размер * log, ну а всего таких запросов не больше m.
Если размер маленькой больше корня, то суммарно это не больше чем $$$O(n \sqrt n \log n)$$$, ведь для каждой такой (у которой размер больше корня) есть всего $$$O(\sqrt n)$$$ пар.