## DS1. Сортировка подстрок :::spoiler Подсказка :::info После сортировки подстроки все вхождения одной буквы будут находиться на непрерывном подотрезке этой подстроки. ::: :::spoiler Разбор :::info В вершине дерева отрезков будем поддерживать массив количеств всех букв. Чтобы отсортировать подстроку $[l; r]$, получим её массив количеств $cnt$. Пусть $sum(x) = cnt_0 + cnt_1 + ... + cnt_x$ т.е. префиксная сумма массива количеств. Тогда буква $x$ в отсортированной подстроке будет находиться в отрезке $[sum(x - 1), sum(x - 1) + kol_x - 1]$. Сделаем в ДО присвоение на этом отрезке. Асимптотика: $O(q \cdot log(n) \cdot 26)$. ::: ## DS2. Ярослав и делители :::spoiler Подсказка 1 :::info Так, как по условию дана перестановка, количество различных пар $(a, b)$ где $a$ - делитель $b$, будет порядка $n + \frac{n}{2} + \frac{n}{3} + \ldots = n \cdot log(n)$ ::: :::spoiler Подсказка 2 :::info Отсортируем запросы по $r$. На каждом шаге $i$ алгоритма ответим на все запросы, у которых $r = i$, и перейдём от $i$ к $i + 1$. ::: :::spoiler Решение :::info При переходе от $i$ к $i + 1$ найдём все числа $x$, которые делятся на $p_{i + 1}$ или являются делителями $p_{i + 1}$. Тогда для каждого $x$, который в исходном массиве находится левее $p_{i + 1}$, прибавим в дереве Фенвика на его позиции $1$. Тогда на $i$-м шаге алгоритма ответ для отрезка $[l; i]$ равен сумме на отрезке $[l; i]$. Асимптотика: $O(n \cdot log^2 n)$. ::: ## DS3. О меняющемся дереве :::spoiler Подсказка :::info Воспользуемся идеей префиксных сумм. Пусть $dist(a, b)$ -- расстояние от $a$ до $b$. Тогда если $b$ находится в поддереве $a$, то $dist(a, b) = dist(1, b) - dist(1, a)$. ::: :::spoiler Решение :::info Построим эйлеров обход, тогда поддереву каждой вершины соответствует непрерывный подотрезок. Посчитаем для каждой вершины $v$ расстояние от неё до корня $h_v$. Будем поддеживать два дерева отрезков. При запросе изменения в первом ДО добавим на отрезке, соответствующем поддереву вершины $v$, $x + h_v \cdot k$, а во втором ДО на том же отрезке добавим $k$. Тогда, если обозначим первое ДО как $st1$, второе ДО как $st2$, то при запросе второго типа в вершине $v$ нужно вывести $st1.get(v) - st2.get(v) \cdot h_v$. Асимптотика: $O(q \cdot log(n))$. ::: ## DS4. Сумма XOR :::spoiler Подсказка 1 :::info Решайте задачу для каждого бита отдельно. Для каждого бита $i$ посчитайте количество подотрезков, xor которых содержит $1$ в $i$-м бите. ::: :::spoiler Подсказка 2 :::info Чтобы $i$-й бит в xor на подотрезке был равен $1$, нужно, чтобы в этом подотрезке было нечётное число элементов с $1$ в $i$-м бите. Тогда мы свели задачу к следующей: дан массив из нулей и единиц, нужно быстро считать на отрезке $[l; r]$ количество подотрезков с нечётной суммой. ::: :::spoiler Решение :::info В вершине дерева отрезков будем поддерживать следующие переменные: $ans$ -- количество подотрезков с нечётной суммой $pref0$, $pref1$ -- количество префиксов с чётной / нечётной суммой $suf0$, $suf1$ -- количество суффиксов с чётной / нечётной суммой $sum$ -- сумма всех чисел в подотрезке Чтобы объеденить ответ в вершинах $l$ и $r$: $ans = l.ans + r.ans + l.suf0 \cdot r.pref1 + l.suf1 \cdot r.pref0$ $pref0 = l.pref0 + r.pref0$ (если $l.sum$ чётная) $pref0 = l.pref0 + r.pref1$ (иначе) Аналогично поддерживается $pref1$, $suf0$ и $suf1$. Асимптотика: $O(q \cdot log(n) \cdot log(max(a_i)))$ ::: ## DS5. Мощный процессор :::spoiler Подсказка 1 :::info $dp[size][lst]$ -- минимальный индекс элемента, на котором заканчивается возрастающая подпоследовательность длины $size$ с последним элементом $\le lst$. ::: :::spoiler Подсказка 2 :::info $dp[size][lst] = min(dp[size][lst - 1], after(dp[size - 1][lst - 1], lst))$, где $after(k, x)$ -- минимальный индекс элемента, равного $x$, правее $k$. Как быстро считать $after(k, x)$? ::: :::spoiler Решение :::info В вершне дерева отрезков будем хранить количество каждого числа от $0$ до $7$. Операция $xor$ делается при помощи ленивого обновления. $after(i, x)$ можно найти двоичным спуском по ДО. Асимпотика: $O(q \cdot log(n) \cdot 64)$. ::: ## SQ1. Магазин песочых часов :::spoiler Подсказка :::info Рассмотрите случаи когда $b_i \le \sqrt{t}$ и когда $b_i > \sqrt{t}$. ::: :::spoiler Разбор :::info Для случая $b_i \le \sqrt{t}$ будем поддерживать массив $cnt[x][mod]$ - количество часов с интервалом $x$, появившихся в момент, дающий по модулю $x$ остаток $mod$. Тогда в момент времени $i$ мы прибавим к ответу все $cnt[j][i \mod j]$. В случае $b_i > \sqrt{t}$ моментов времени, на которые повлияют эти часы, будет не больше $t / \sqrt{t} = \sqrt{t}$, значит можно перебрать все такие моменты времени и прибавить к ответу в них $1$. Асимптотика: $O(n \cdot \sqrt{t}).$ ::: ## SQ2. Ленты конвейера :::spoiler Подсказка :::info Пусть $k = \sqrt{n m}$. Разобьём таблицу на $k$ блоков по горизонтали. ::: :::spoiler Решение :::info Будем поддерживать $pos[i][j]$ -- позицию, в которую мы попадём из клетки $(i, j)$, когда выйдем из текущего блока. Тогда ответ на запрос типа $A$ можно посчитать за $O(k)$. После обновления в точке нужно пересчитать все значения $pos[i][j]$ в её блоке. Это можно сделать за $O(nm / k) = O(k)$ рекурсией с мемоизацией. Асимптотика: $O(q \cdot \sqrt{nm})$. ::: ## SQ3. Суммы подмножеств :::spoiler Подсказка 1 :::info Пусть $S$ - сумма размеров всех множеств. Назовём лёгкими множества размера $\le \sqrt{S}$ и тяжёлыми множества размера $> \sqrt{S}$. Тогда всего тяжёлых множеств будет не больше $S / \sqrt{S} = \sqrt{S}$. ::: :::spoiler Подсказка 2 :::info Чтобы эффективно отвечать на запросы, для каждого множества (как лёгкого, так и тяжёлого) посчитаем размеры его пересечения со всеми тяжёлыми множествами. Это можно сделать за время $O(n \sqrt{S})$. Для каждого тяжёлого множества создадим битсет размера $n$, в $i$-ой ячейке которого будем хранить, сколько элементов $i$ в этом множестве. Затем для каждого элемента и каждого тяжёлого множества будем за $O(1)$ проверять, содержится ли элемент в тяжёлом множестве. ::: :::spoiler Решение :::info Рассмотрим 4 возможных запроса: - Добавление к лёгкому множеству. Пройдем по всем числам множества и к каждому добавим нужное значение. Дальше пройдем по всем тяжелым множествам и к каждому добавим (размер пересечения * значение в запросе). Время работы $O(\sqrt{S})$. - Добавление к тяжелому множеству. Просто увеличим счетчик для данного тяжелого множества на значение в запросе. Время работы $O(1)$. - Ответ на запрос для лёгкого множества. Проходим по всем числам, добавляем значения к ответу. Затем проходим по всем тяжёлым множествам и добавляем к ответу (добавление для данного тяжёлого множества * размер пересечения с множеством в запросе). Время работы $O(\sqrt{S})$. - Ответ на запрос для тяжелого множества. Берем уже посчитанный ответ, затем проходим по тяжелым множествам и добавляем (добавление для данного тяжелого множества * размер пересечения со множеством в запросе). Время работы $O(\sqrt{S})$. Асимптотика: $O(q \cdot \sqrt{S})$. :::