## DS1. Интересный массив :::spoiler Подсказка 1 :::info Решайте задачу для каждого бита отдельно. ::: :::spoiler Подсказка 2 :::info Если в каком-либо ограничении $k$-ый бит равен $1$, то и во всех числах на отрезке он должен быть равен $1$. ::: :::spoiler Разбор :::info Будем решать задачу отдельно для каждого бита. Предположим, что пришло новое ограничение: $l_i$, $r_i$, $q_i$. Если в числе $q_i$ бит с номером pos единичный, то у всех чисел на отрезке $[l_i, r_i]$ этот бит тоже будет единичным. Теперь можно воспользоваться стандартной идеей прибавления на отрезке оффлайн. Сделаем два прибавления в массиве $s[bit]$ — в позиции $l_i$ мы сделаем прибавление $1$, а еще одно в позиции $r_i + 1$, там мы прибавим $-1$. Таким образом, если мы насчитаем префиксные суммы на массиве $s[bit]$, то, если $s[bit][i] > 0$, то бит $bit$ в этом числе будет единичным, иначе — нет. После этого можно реализовать дерево отрезков, чтобы проверить выполнимость изначальных запросов. Асимптотика: $O(n\log{n}\log max(q_i))$. ::: ## DS2. Бесконечные инверсии ::: spoiler Подсказка ::: info Для каждой позиции, которую как-то изменяли swap-ы, посчитайте число, которое будет там стоять после применения всех swap-ов. Посмотрите, какие инверсии образуют числа на всех таких позициях. ::: ::: spoiler Разбор ::: info Запомним, на какой позиции какое число будет стоять после выполнения всех swap-ов. Теперь будем считать ответ. Ответ состоит из двух частей. Первая часть — это инверсии, образованные исключительно теми элементами, которые поучаствовали в swap-ах. Их можно посчитать с помощью ordered set. Вторая часть — это инверсии, в которых один из элементов пары участвовал в swap-ах, а второй — нет. Для простоты рассмотрим тест: $2$ $2$ $6$ $4$ $8$ Перестановка будет выглядеть так: $[1, 6, 3, 8, 5, 2, 7, 4, 9, ...]$, а массив swap-нутых элементов так: $[6, 8, 2, 4]$. Давайте поймем, с какими элементами будет образовывать инверсии число 8. Очевидно, такими элементами могут быть лишь те элементы, которые находятся между начальной позицией числа $8$ (где сейчас число $4$), и текущей его позицией. Вот этот подотрезок: $[5, 2, 7,]$. Чисел на этом подотрезке, которые не участвовали в swap-ах, две штуки: $5$ и $7$. Число $2$ учитывать не надо — ведь оно участвовало в swap-ах, и мы его посчитали на первом шаге решения. Таким образом, надо взять количество чисел между начальной и конечной позицией числа $8$ в глобальной перестановке (т.е. $8 - 4 - 1 = 3$), и вычесть из него количество чисел между позициями числа 8 в массиве swap-ов (т.е. $4 - 2 - 1 = 1$). Чтобы избавиться от дополнительного вычитания единицы, можно просто из правого индекса вычитать левый. Так мы получим количество инверсий, образованные элементом 8 и элементами глобальной перестановки, не участвовавших в swap-ах. Для завершения второго шага надо лишь посчитать эту величину для всех чисел, участвовавших в swap-ах. Все операции второго шага можно выполнить при помощи сортировок и бинарного поиска. Асимптотика: $O(n\log{n})$. ::: ## DS3. Водяное дерево ::: spoiler Подсказка ::: info Чтобы проверить, пустая ли вершина $v$, можно посмотреть, была ли опустошена какая-то вершина в поддереве $v$ позже, чем $v$ была заполена водой. Значит, вся задача сводится к запросам на поддеревьях. ::: ::: spoiler Разбор ::: info Пронумеруем все вершины в порядке выхода DFS. Тогда каждому поддереву соответствует один непрерывный отрезок номеров вершин, и запрос на поддереве означает запрос на отрезке в ДО. Создадим два дерева отрезков. В первом для каждой вершины будем хранить максимальный номер запроса, который заполнял эту вершину водой. Во втором - максимальный номер запроса, который опустошал эту вершину (без учёта её предков). С помощью них можно эффективно обрабатывать запросы: 1. Заполнить вершину $v$. В первом ДО присваиваем текущий номер запроса всему поддереву $v$. 2. Опустошить вершину $v$. Во втором ДО присваиваем текущий номер запроса только вершине $v$. 3. Ответить, заполнена ли вершина $v$. В первом ДО получаем значение в вершине $v$, во втором берём максимум в поддереве $v$. Если первое значение больше, то вершина заполнена, иначе пуста. Асимптотика: $O(n\log{n})$. ::: ## DS4. Дерево и запросы ::: spoiler Подсказка ::: info Количество различных $x$ таких, что количество вершин цвета $x$ больше $\sqrt{n}$, будет не больше $\sqrt{n}$. ::: ::: spoiler Разбор ::: info Пусть $kol[v][x]$ - количество вершин цвета $x$ в поддереве вершины $v$. Разберём случаи, когда $kol[v][x] < \sqrt{n}$ и $kol[v][x] \ge \sqrt{n}$. Чтобы решить первый случай, посчитаем $cnt[v][k]$ - количество различных цветов $x$ таких, что $kol[v][x] = k$ и $k < \sqrt{n}$. Для второго случая будем для каждой вершины $v$ хранить $lst[v]$ - вектор всех цветов, количество которых больше $\sqrt{n}$. Таких цветов будет не больше $\sqrt{n}$, значит суммарно $lst$ будет занимать $O(n\sqrt{n})$ памяти. Посчитаем $cnt[v][k]$ и $lst[v]$, поддерживая $map<цвет, количество>$ с помощью Small-to-large. Чтобы ответить на запрос, возьмём сумму на суффиксе $cnt[v]$ и переберём все цвета в $lst[v]$ за $O(\sqrt{n})$. Асимптотика: $O(n\log^2{n} + n\sqrt{n})$. ::: ::: spoiler Другой способ ::: info Построим эйлеров обход и сведём задачу к запросам на отрезке ($l_i, r_i, x_i$). Чтобы её решить, разобьём запросы на $\sqrt{n}$ блоков - в $k$-ом блоке будут все запросы, у которых $l_i / \sqrt{n} = k$. Будем обрабатывать запросы отдельно для каждого блока. Допустим, сейчас мы на блоке $k$. Разберём два случая: 1. $r_i / \sqrt{n} = k$. Всего максимум $\sqrt{n}$ таких запросов, длина отрезка в каждом не превосходит $\sqrt{n}$, значит такие запросы можно обработать за $O(n)$ 2. $r_i / \sqrt{n} > k$. Отсортируем все такие отрезки по левой границе. Тогда выполняется свойство: $l_1 \le l_2 \le ... \le l_m \le r_m \le r_{m-1} \le ... \le r_1$ (по свойству эйлерова обхода). Такие запросы также можно обрабатывать за $O(n)$, если поддерживать массив количеств и суффиксные суммы на нём. Асимптотика: $O(n\sqrt{n})$. ::: ## DS5. Цветной граф мистера Китаюта ::: spoiler Разбор ::: info Для каждого цвета сделаем СНМ, в котором будут все рёбра этого цвета. С помощью него можно проверять, достижимы ли вершины $a$ и $b$ с помощью определённого цвета. Для каждого запроса ($a_i, b_i$) выберем из $a_i$ и $b_i$ вершину с наименьшей степенью, переберём цвета всех выходящих из неё рёбер и проверим связность в СНМ для этих цветов. Запомним ответ на запрос ${a_i, b_i}$. Если опять приходит такой же запрос, выводим уже посчитанный ответ. Асимптотика: $O(m\sqrt{q})$. ::: ::: spoiler Доказательство ::: info Пусть $deg(v)$ - степень вершины $v$. Тогда на запрос ($a_i, b_i$) ($deg(a_i) \le deg(b_i)$) мы отвечаем за $O(deg(a))$. Тогда в худшем случае все запросы - все возможные пары из $\sqrt{q}$ вершин с максимальной степенью. Зафиксируем вершину $a$ в паре, переберём вершину $b$. Тогда суммарное время работы для всех $b$ равно $O(\sum{deg(v)}) = O(m)$. Всего $\sqrt{q}$ возможных $a$, значит суммарное время работы - $O(m\sqrt{q})$. ::: ::: spoiler Другой способ ::: info Пронумеруем все компоненты связности с рёбрами одного цвета. Для каждой вершины $v$ охраним $comp[v]$ - bitset из всех компонент связности, которым принадлежит эта вершина. Тогда ответ для вершин $a$ и $b$ - это количество единичных битов в $comp[a] \& comp[b]$. Асимптотика: $O(q\frac{m}{64})$. :::