Разбор задач. День 12. Корней Корнеевич

Задача А. RMQ

Разделим массив $$$A[0..n-1]$$$ на $$$\sqrt{N}$$$ блоков. Будем поддерживать массив $$$Block[0..\sqrt{N}]$$$, где $$$i$$$-й элемент будет минимальным значением $$$i$$$-го блока. Каждому блоку изначально установим значение $$$+\infty$$$. При считывании исходного массива $$$A$$$ в каждом блоке будем поддерживать минимальное значение:

$$$Block[i] = \underset{j \in [\space i * \sqrt{N}; (i+1) * \sqrt{N}) \space}{\min{A[j]}}$$$

Будем отвечать на запрос поиска минимума на полуинтервале $$$[l; r)$$$ за $$$O(\sqrt{N})$$$, проходясь по блокам, полностью входящим в запрос, а также наивно проходясь по элементам блоков, частично входящих в запрос.

На запрос присвоения нового значения в ячейке массива будем отвечать также за $$$O(\sqrt{N})$$$ путём присвоения нового значения в массиве и пересчёта значения блока.

Если запросов всего $$$Q$$$, то итоговая асимптотика решения составляет $$$O(Q * \sqrt{N})$$$.

Задача B. Тройки

Введём понятие лёгкие/тяжёлые вершины. Если вершина $$$u$$$ имеет меньше $$$\sqrt{M}$$$ соседей, будем считать её лёгкой, а иначе — тяжёлой:

$$$ g[u]| \lt \sqrt{M}: u - \text{лёгкая} $$$ $$$ g[u]| \ge \sqrt{M}: u - \text{тяжёлая} $$$

Заметим, что тяжёлых вершин $$$\le\sqrt{M}$$$.

Будем также поддерживать список смежности, содержащего только тяжёлых соседей $$$T[u] = \langle v| v \in g[u] \wedge \big|g[v]\big| \ge \sqrt{M} \rangle$$$

Оба списка смежности отсортируем для последующего применения метода двух указателей.

Разделим тройки вершин на 4 типа, в зависимости от количества содержащихся в ней лёгких и тяжёлых вершин: ЛЛЛ, ЛЛТ, ЛТТ, ТТТ. Будем насчитывать каждый тип циклов отдельным способом.

Чтобы насчитать тройки ЛЛЛ и ЛЛТ, пройдёмся циклом по всем рёбрам за $$$O(M)$$$ и для каждой пары ЛЛ лёгких вершин пройдёмся двумя указателями по их соседям. Поскольку соседей у лёгких вершин $$$ \lt \sqrt{M}$$$, то асимптотика поиска ЛЛЛ и ЛЛТ составит $$$O(M * \sqrt{M})$$$.

Для подсчёта троек ЛТТ и ТТТ поступим похожим образом: переберём все рёбра ЛТ и ТТ, теперь переберём всех их тяжёлых соседей двумя указателями. Поскольку тяжёлых вершин $$$\le\sqrt{M}$$$, то сложность подсчёта ЛТТ и ТТТ составит $$$O(M * \sqrt{M})$$$.

Итоговая асимптотика решения $$$O(M * \sqrt{M})$$$. Заметим, что число троек циклов в графе не больше $$$M * \sqrt {M}$$$, это следует из алгоритма решения.

Задача C. Фаброзавры-дизайнеры

Разделим массив $$$A[0..n-1]$$$ на $$$\sqrt{N}$$$ блоков по $$$\sqrt{N}$$$ элементов $$$Block[0..\sqrt{N}]$$$. Также заведём массив $$$add[0..\sqrt{N}]$$$, в котором для каждого блока будем хранить значение, на которое нужно изменить каждый его элемент. В каждом блоке будем хранить элементы в отсортированном виде для того, чтобы в будущем мы могли применить бинпоиск для поиска нужного значения:

$$$ Block[i] = \{X_1, X_2, \dots, X_\sqrt{N}\}, \space X_1 \le X_2 \le \dots \le X_\sqrt{N} $$$

Будем отвечать на запрос изменения на полуинтервале $$$[l; r)$$$ за $$$O(\sqrt{N})$$$ проходясь по каждому блоку:

Если блок $$$Block[i] = [d; d + \sqrt{N})$$$ полностью входит в запрос $$$[l; r)$$$, то прибавим значение к $$$add[i]$$$.
Если блок $$$[d; d + \sqrt{N})$$$ частично входит в запрос $$$[l; r)$$$, то изменим каждое значение в блоке поэлементно и после обработки этого блока заново его отсортируем

Сложность обработки такого запроса составит $$$O(\sqrt{N}*\log{\sqrt{N}})$$$

Для того, чтобы отвечать на запрос поиска значения $$$X$$$ на полуинтервале $$$[l; r)$$$ снова обработаем каждый блок:

Если блок $$$Block[i] = [d; d + \sqrt{N})$$$ полностью входит в запрос $$$[l; r)$$$, то попробуем найти бинпоиском значение $$$X - add[i]$$$ за $$$O(\log{\sqrt{N}})$$$.
Если блок $$$[d; d + \sqrt{N})$$$ частично входит в запрос $$$[l; r)$$$, то просто пройдёмся по каждому элементу этого блока в исходном массиве и посмотрим на его равенство с $$$X - add[i]$$$.

Таким образом, если запросов всего $$$Q$$$, то итоговая асимптотика решения составит $$$O(Q * \sqrt{N} * \log{\sqrt{N}})$$$

Задача D. Мистер Бин и газета

Обратим внимание на ограничения $$$N$$$ и $$$M$$$: $$$N * M \le 10^5$$$. Разделим решение задачи на случаи, когда $$$N \lt M$$$ и $$$N \gt M$$$.

Случай, когда $$$M \lt N: M \lt \sqrt{N*M} \le \sqrt{10^5}$$$. Поскольку элементов в каждой строке немного, то будем обрабатывать каждый запрос отдельно и прибавлять каждый элемент одной строки каждому элементу другой строки. Асимптотика решения такого частного случая составит $$$O(K * \sqrt{N*M})$$$

Случай, когда $$$M \lt N: N \lt \sqrt{N*M} \le \sqrt{10^5}$$$. Обозначим исходную таблицу $$$Source_{N\times{M}}$$$, а итоговую таблицу $$$Answer_{N\times{M}}$$$ — ответ на задачу. Поскольку у нас мало строк, то будем хранить матрицу отношений между строками

$$$C_{N\times{N}} = \begin{bmatrix} 1&0&0&\dots&0 \\ 0&1&0&\dots&0 \\ 0&0&1&\dots&0 \\ \dots&\dots&\dots&\dots&\dots \\ 0&0&0&\dots&1 \\ \end{bmatrix}$$$

, где элемент $$$C_{ik}$$$ обозначает сколько раз нужно добавить $$$k$$$-ю строку исходной таблицы к $$$i$$$-й строке результирующей таблицы:

$$$ Answer[i][j] = \underset{k\in[1..N]}{\sum}{Source[k][j]} $$$

Теперь будем обрабатывать запрос добавления строки $$$x$$$ к строке $$$y$$$ следующим образом: каждому элементу строки $$$y$$$ результирующей таблицы прибавим значение соответствующий элемент строки $$$x$$$ той же таблицы:

$$$ C[y][j] = C[x][j] + C[y][j], j \in [1..N] $$$

Поскольку элементов в каждой строке $$$N \le \sqrt{N*M}$$$, то на каждый такой запрос будем отвечать за $$$O(\sqrt{N*M})$$$. В конце посчитаем итоговую таблицу $$$Answer$$$ по вышеописанной формуле за $$$O(M*\sqrt{N} * \sqrt{N})=O(N*M)$$$:

Итоговая асимптотика решения составит $$$O(N*M + K*\sqrt{N*M})$$$

Задача E. И снова сумма

Заметим, что операций $$$N \le 3 * 10^5$$$. Поскольку изначально множество $$$S$$$ пустое, то в каждый момент времени размер этого множества не будет превосходить количества выполненных операций $$$|S| \le N$$$.

Для обработки запросов будем поддерживать корневую структуру данных: $$$\le \sqrt{N}$$$ блоков, каждый из которых содержит $$$\le \sqrt{N}$$$ элементов. Каждый блок будет представлять из себя список элементов, следующих друг за другом в неубыващем порядке. Иными словами, мы делим один большой список с упорядоченными элементами на несколько маленьких списков. Будем также поддерживать массив для каждого блока сумму его элементов: при добавлении элемента в список будем добавлять это же значение в сумму, а при удалении — вычитать. Теперь, чтобы посчитать сумму на отрезке значений элементов множества, пройдёмся по каждому блоку:

Если первый элемент блока (он же наименьший) и правый (он же наибольший) полностью входят в отрезок запроса, то прибавляем к ответу сумму блока.
Если отрезок значений частично входят в запрос, то проитерируемся по элементам этого блока за $$$O(\sqrt{N})$$$

Чтобы отвечать на запрос добавления элемента, пройдёмся по блокам и выберем из них тот, куда мы можем добавить элемент, чтобы сохранить общую упорядоченность элементов по всем блокам, а также поставим этот элемент на такую позицию, чтобы сохранить упорядоченность среди элементов внутри блока. Это можно сделать за $$$O(\sqrt{N})$$$. После того, как мы добавим элемент внутрь блока, количество содержащихся в нём элементов увеличится на единицу и может возникнуть ситуация, при котором их станет $$$\sqrt{N} + 1$$$. В таком случае переместим последний элемент списка (наибольший элемент блока) в начало следующего списка (так он станет наименьшим элементом следующего блока). Такое перемещение выполняется за $$$O(1)$$$, поскольку мы используем списки в качестве контейнера. Теперь, в случае, если в новом блоке элементов стало также $$$\sqrt{N} + 1$$$, то продолжим эти перетаскивания, пока во всех блоках элементов не станет $$$\le \sqrt{N}$$$. Поскольку всего блоков $$$\le \sqrt{N}$$$, то перетаскиваний элементов между блоками будет также $$$\le \sqrt{N}$$$. Асимптотика добавления элемента составляет $$$O(\sqrt{N})$$$

Итоговая асимптотика решения: $$$O(N*\sqrt{N})$$$

Задача G. Суровый корректор

Пусть суммарная длина строк равна $$$M$$$. Разделим строки на 2 типа: лёгкие (длина $$$\le \sqrt{M}$$$) и тяжёлые (длина $$$\gt \sqrt{M}$$$). Заметим, что тяжёлых строк $$$\le \sqrt{M}$$$.

Для больших строк просто проитерируемся по всем подотрезкам уже известной длины. Чтобы быстро сравнивать подстроки, воспользуемся хэшами и префиксными суммами, таким образом сравнение можно сделать за $$$O(1)$$$. Всего тяжёлых строк $$$O(\sqrt{M})$$$, возможных подстрок исходной строки $$$O(N)$$$, получаем асимптотику $$$O(N * \sqrt{M})$$$.

Чтобы уметь отвечать на лёгкие запросы, заранее насчитаем хэши подстрок для каждой из $$$\sqrt{M}$$$ возможных длин. Хранить хэши можно в хэш-таблицах или двумерном массиве. Тогда время препроцессинга займёт $$$O(N*\sqrt{M}*\log{\sqrt{M}})$$$ либо $$$O(N*\sqrt{M})$$$ в зависимости от способа реализации.

Итоговая асимптотика решения $$$O(N*\sqrt{M})$$$.

Задача H. Лунки

Сначала научимся решать задачу в случае, когда нам приходят запросы только второго типа. Будем поддерживать $$$dp[i] = \langle cnt, last \rangle$$$, где $$$cnt$$$ — количество прыжков, которые сделает шарик, прежде чем вылетит за границу, если её забросить в $$$i$$$-ю лунку, а $$$last$$$ — номер последней лунки, в которой окажется шарик.

Переходы опишем следующим образом:

$$$ \begin{align*} & dp[i] = \langle 1, i \rangle, i + a[i] \gt n \\ & dp[i] = \langle dp[i + a[i]][0] + 1, dp[i + a[i]][1] \rangle, i + a[i] \le n \end{align*} $$$

Порядок обхода рассчёта $$$dp$$$ будет производиться справа налево. Теперь, чтобы ответить на запрос второго типа, достаточно просто вывести содержимое $$$dp[i]$$$. Заметим, что подсчёт ДП производится всего за $$$O(N)$$$.

Чтобы уметь обрабатывать запросы первого типа, разделим весь массив элементов на $$$\sqrt{N}$$$ блоков. Для каждого блока изолированно насчитаем отдельно свой массив $$$dp$$$, как если бы это и был весь массив. Все эти манипуляции можно произвести за линейное время. Теперь, при изменении элемента будем пересчитывать ДП блока, к которому элемент относится за $$$O(\sqrt{N})$$$. Чтобы отвечать на запрос второго типа, будем итерироваться с $$$i$$$-го элемента: получим пару $$$\langle cnt, last \rangle$$$, добавим $$$cnt$$$ к общему числу прыжков, и продолжим прыжки с позиции $$$last + a[last]$$$. Заметим, что прыжок по $$$dp$$$ будет шарик вести в новый блок. Поскольку всего блоков $$$\le \sqrt{N}$$$, то число больших прыжков также составлять не больше этого числа.

Итоговая асимптотика полученного решения составляет $$$O(M * \sqrt{N})$$$.

Задача I. Проверка эксперимента

Данная задача разобрана во время лекции, поэтому будет кратко приведена идея решения.

Воспользуемся алгоритмом Мо: разделим последовательность на $$$\sqrt{N}$$$ блоков, сохраним все запросы с их номерами (для последовательного вывода ответа) в какой-нибудь массив и сгруппируем эти запросы по левым границам, отсортировав их в каждой группе по правым границам. Теперь достаточно пройти по всем запросам, поддерживая левую и правую границу рассматриваемого отрезка, а также внешние структуры для подсчёта количества элементов и количества элементов, встречающихся определённое количество раз.

Для подсчёта количества элемента будем поддерживать массив $$$cnt[N]$$$, при сдвиге одной из границ рассматриваемого отрезка операция изменения $$$cnt$$$ будет работать за $$$O(1)$$$.

Чтобы поддерживать число встречающихся элементов для каждого отрезка, можно поддерживать ДО, тогда операция изменения при сдвиге одной из границ будет составлять $$$O(\log{N})$$$. Заметим, что сдвигов границ рассматриваемого отрезка будет $$$O(Q*\sqrt{N})$$$, тогда суммарная сложность обработки границ будет составлять $$$O(Q * \sqrt{N} * \log{N})$$$. Для ответа на запрос достаточно просто взять сумму в ДО на отрезке $$$[x; y]$$$, что суммарно даёт асимптотику $$$O(Q * \log{N})$$$.

Можно улушчить асимптотику до $$$(Q * \sqrt{N})$$$. Для этого вместо ДО будем поддерживать корневую структуру, где операция изменения составляет всего $$$O(1)$$$, а запрос суммы $$$O(\sqrt{N})$$$.