Общая концепция листка

В этом листке почти во всех задачах такой сюжет: есть массив данных, организованных в одномерный/двумерный массив или граф. И есть набор запросов, который предполагает вычисление некоторой функции на отрезке/прямоугольнике. В худшем случае возможно ещё и изменение данных.

Что почитать по теме

Предподсчёт на всех префиксов

Часто функция обладает таким полезным свойством: ответ множестве $X$ может быть легко вычислен на основе ответа на множестве $X\cup Y$ и на множестве $Y$. Если предпосчитать достаточно богатый набор значений функции, то потом можно быстро давать ответы.

Пример такой функции — сумма всех элементов множества.

Для подобный функций бывает полезно предпосчитать её значения на всех префиксах или всех суффиксах, или на всех подпрямоугольниках с вершиной в каком-нибудь угле данных.

A: Суммы на префиксе

Дан массив $A$ длины $N$, а также $M$ запросов вида $l$. Для каждого запроса найдите сумму первых $l$ элементов массива.

4 4 1 2 3 4 1 2 3 4
1 3 6 10

B: Суммы на подотрезках

Дан массив $A$ длины $N$, а также $M$ запросов вида $l$ $r$. Нужно найди сумму элементов массива с $l$ по $r$

4 3 1 2 3 4 1 4 2 4 2 3
10 9 5

C: Произведение на подотрезках

Дан массив $A$ длины $N$, а также $M$ запросов вида $l$ $r$. Нужно найди произведение элементов массива с $l$ по $r$ по модулю $10^9 + 7$. Гарантируется, что в массиве нет нулей.

4 3 1 2 3 4 1 4 2 4 2 3
24 24 6

D: Суммы на подпрямоугольнике

Дан двумерный массив $A$ размера $N \times M$, а также $Q$ запросов вида $x\ y\ x_1\ y_1$. Нужно найди сумму элементов подмассива с левым верхним углом в $(x, y)$ и правым нижним $(x_1, y_1)$

3 3 2 1 2 3 4 5 6 7 8 9 2 2 3 3 1 1 2 3
28 21

Изменения

Вообще, идея префиксных предподсчетов довольно часто возникает в программировании, но у данного подхода есть как плюсы (например, ответ за $O(1)$), так и минусы, например, изменение элементов происходит за $O(n)$, что очень долго. Научимся за не слишком медленно изменять элементы, не сильно замедлив процедуру ответа.

Идея несколько похожа на идею префиксного подсчета: давайте поделим весь массив на блоки размера $k$, в каждом из которых посчитаем ответ и запишем в массив $blocks$. Теперь научимся получать ответ. Пусть есть запрос на вычисление функции на отрезке с $l$ по $r$. Выделим внутри этого отрезка полные блоки, и добавим их в ответ, а "хвост" обработаем руками. Суммарная ассимптотика $O(n / k + k)$. Оказывается, самым оптимальным значением для $k$ есть $\sqrt n$

Теперь заметим, что изменение работает за $O(1)$. Изменив элемент и ответ в соответствующем блоке мы полностью обновим структуру.

E: Суммы на подотрезках с единичным изменением

Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:

  1. сумма на отрезке
  2. единичное изменение
Требуется ответить на все запросы суммы на отрезке
4 3 1 2 3 4 1 1 3 2 2 10 1 1 3
6 14

F: Произведение на подотрезках с единичным изменением

Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:

  1. произведение на отрезке по модулю $10^9 + 7$
  2. единичное изменение

Требуется ответить на все запросы произведения на отрезке. Гарантируется, что во всех версиях массива нет нулей

4 3 1 2 3 4 1 1 3 2 2 10 1 1 3
6 30

G: Суммы на подотрезках с изменением на отрезке

Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:

  1. сумма на отрезке
  2. инкремент на отрезке

Требуется ответить на все запросы суммы на отрезке

5 3 1 2 3 4 5 1 1 5 2 2 5 3 1 1 5
15 27
Подсказка
Да что-то непонятное тут требуют...

Храни вспомогательный массив для блоков.

Тут какая-то жесть

Давате хранить вспомогательный массив $add$ длиной $\sqrt n$ в каждой ячейке которого будем хранить насколько суммарно мы увеличили все числа в данном блоке. Теперь обновление выглядит так: ищем "цельные" блоки, увеличиваем суммарный инкремент, а "хвост" обрабатываем руками.

Хранение дополнительной информации в декомпозиции

Часто, бывает удобно хранить вспомогательную структуру внутри декомпозиции, например, массив инкрементов на блоках. В следующих задачах вам предстоит самим догадаться, какие именно доп.структуры надо использовать.

H: Количество чисел меньших $k$ с инкрементом на отрезке

Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа. Запрос первого типа – вычислить количество элементов массива на отрезке от l до r меньших заданного числа x. Запрос второго типа – увеличить все элементы массива на отрезке от l до r на заданное число x.

  1. 1 - найти количество чисел меньших $k$ и больших $l$ на отрезке
  2. 2 - инкремент на отрезке на величину $x$

Требуется ответить на все запросы.

5 3 1 2 3 4 5 1 1 5 5 2 2 4 2 1 1 5 5
4 2

I: K-я порядковая статистика на отрезке с изменением на отрезке

Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа.

  1. Вычислить $k$-тую порядковую статистику на отрезке с $l$ по $r$.
  2. Увеличить все элементы массива на отрезке от $l$ до $r$ на заданное число x.
5 2 1 2 3 4 5 1 1 5 5 2 2 4 2
8

Корневая не как структура

Корневая декомпозиция на графах

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

J: Покраска вершин

Вам дан граф с $N$ вершинами и $M$ ребрами. У каждой вершины есть свой цвет $v_i$. Вам дано $q$ запросов в виде пары $(v_i, c_i)$, означающий, что надо перекрасить вершину $v_i$ в цвет $c_i$. После каждого запроса нужно вывести количество ребер у которых вершины покрашены в разный цвет.

4 5 1 2 3 4 1 2 2 3 3 4 4 1 1 3 5 1 5 3 2 4 4 1 4 2 3
5 4 4 3 4

K: Количество соседних цветов

Дан неориентированный граф без петель и кратных ребер, у которого $n$ вершин и $m$ ребер. У каждой вершины есть цвет. Требуется ответить на $q$ запросов. Каждый запрос имеет один из двух типов:

  1. $v$ $c$ – перекрасить вершину $v$ в цвет $c$
  2. $v$ – вычислить количество различных цветов у соседей вершины $v$.
4 3 3 1 2 3 4 1 2 1 3 1 4 2 1 1 4 3 2 1
3 2

L: Количество циклов длины 3

Вам дан граф с $N$ вершинами и $M$ ребрами. Вам нужно найти количество циклов длины 3.

6 6 1 2 2 3 3 1 4 2 3 4 5 1
2

M: Очень простая сумма

Дано число $n$ до $10^{12}$, посчитайте сумму $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$

5
10
1000000000000
27785452449086

Корневая декомпозиция на строках

Разбиение на тяжелые и легкие

Назовем строку $S$ длинной, если $|S| \ge \sqrt{\sum|S|}$. Все оставшиеся строки назовем легкими.

$\textbf{Утверждение.}$ Существует не более $2\sqrt{\sum|S|}$ тяжелых строк.
$\textbf{Доказательство.}$ Пусть существуют более $2\sqrt{\sum|S|}$. Тогда их суммарная длина больше, чем $\frac{2\sqrt{\sum{|S|}}\sqrt{\sum{|S|}}}{2} = \sum{|S|}$, что противоречит условию.

Количество разных длин

$\textbf{Утверждение.}$ Существует не более $\mathcal{O}(\sqrt{\sum|S|})$ различных длин.
$\textbf{Доказательство.}$ Пусть оно равно $x$. Тогда минимально возможная сумма длин - это сумма чисел от 1 до $x$. $\sum_{1}^{x} = \frac{x(x + 1)}{2}$. Так как это число должно быть меньше, чем $\sum{|S|}$, то $x = \mathcal{O}(\sqrt{\sum{|S|}})$

N: Substring query

У Пупы есть $n$ строк $S_1,S_2,S_3,...,S_n$ Однажды его друг Лупа пришёл в бухгалтерию и попросил его ответить на $q$ вопросов: сколько строк среди $S_{l_i},S_{l_i + 1}, S_{l_i + 2},...,S{r}$ содержат $P_i$ как подстроку?

Но в бухгалтерии все перепутали, и ответить на запросы за Пупу придется Вам.

Суммарный размер строк $P_i\le200000$

4 2 a b ab bab 1 3 a 1 4 ab
2 2

Корневая декомпозиция на запросах

Некоторые запросы обновления можно легко обрабатывать группой, например сделав scanline, но тяжело обрабатывать по одному. В таких случаях можно откладывать их выполнение, и запоминать их в какой-нибудь список. При размере списка $\mathcal{O}(\sqrt{n})$ можно обработать все запросы этого списка группой. При выполнении get-запросов достаточно смотреть на все запросы внутри списка и смотреть, как они влияют на ответ

O: Винни Пух и бочки меда

Малыш и Карлсон решили пойти на прогулку. Они знают, что прогулка будет совсем скучной, если перед ней не опустошить несколько банок варенья.
Малыш достал из кладовки N банок варенья и выставил их в ряд. В банке номер $i$ содержится ровно a $i$ грамм варенья. Карлсон немного подумал и решил, что в некоторых банках недостаточно варенья, и что в банке номер $i$ должно быть хотя бы $b_i$ грамм варенья.
Выходить из этой ситуации Карлсон хочет в $M$ этапов. На каждом этапе он выбирает числа $l$, $r$, $x$ и $y$, а затем выполняет следующие операции: в банку номер $l$ он добавляет x грамм варенья, в банку номер $l +  1$ — $x + y$ грамм варенья, в банку номер $l + 2$ — $x + 2· y$, и так далее. В банку номер $r$ наш герой добавит $x + y ·(r - l)$ грамм варенья.
Малышу хочется определить для каждой банки i наименьший номер операции, после которой в ней станет хотя бы b i грамм варенья. Помогите Малышу: найдите соответствующее число для каждой банки.

В первой строке входного файла задано одно число $N (1 ≤ n ≤ 10^{5})$ — количество банок. Во второй строке заданы $N$ чисел $a_i (0 ≤ a_i ≤ 2·10^{9})$ — изначальное количество варенья в банке номер $i$. В третьей строке заданы $N$ чисел $b_i$ $(0 ≤ b_i ≤ 2·10^{9})$ — минимальное количество варенья, которое должно быть в банке номер $i$.
В четвертой строке задано $M$ $(0 ≤ M ≤ 10^{5})$ — число этапов добавления варенья в банки, которые выполнит Карлсон. В следующих $M$ строках описаны сами этапы в хронологическом порядке. Каждый этап задан четырьмя числами $l$, $r$, $x$ и $y$ $(1 \le l \le r \le N, 0 \le x, y \le  10^{5})$.
Выходные данные
Выведите $N$ чисел в одной строке, разделенные пробелом. Число номер $i$ должно быть равно нулю, если в банке номер $i$ изначально было достаточно варенья, номеру этапа, после которого в ней станет хотя бы $b_i$ варенья, или $- 1$, если даже после выполнения всех этапов, в этой банке будет недостаточно варенья. Этапы нумеруются с единицы.

5 5 4 4 2 1 7 7 4 7 7 3 1 2 2 0 2 5 1 1 3 4 2 2
1 2 0 3 -1

Алгоритм Мо

Пусть есть задача на массиве, которую, которую мы умеем решать без запросов обновления, в offline. Запросы могут быть любой степени ужасности, если мы умеем на них отвечать структурой данных, которая хранит информацию об отрезке $[l, r]$ и поддерживает следующие операции:

  1. add_left
  2. add_right
  3. del_left
  4. del_right
  5. query

, которые меняют границы отрезка и внтуреннею структуру данных, а так же позволяют сделать запрос. Все запросы мы пересортируем по паре $(\lfloor \sqrt{l} \rfloor, r)$. Отвечать на запрос мы будем таким образом: с помощью реализованных операций изменим необходимые нам границы отрезка, после чего вызовем запрос query.

Заметим, что левые границы разбиваются по блокам, внутри блока правые границы отсортированы. При переходе от запроса к запросу, левая граница делает $\mathcal{O}(\sqrt{n})$ сдвигов. Правая же граница для запросов одного блока сделает суммарно не более $\mathcal{O}(n)$. Так как общее число блоков $\mathcal{O}(\sqrt{n})$, то и суммарное время работы составляет $\mathcal{O}(n\sqrt{n})$

P: Мощные юнги

Имеется список из $n$ юнг, для каждого из которых известен его рост $a_1,a_2,a_3,...,a_n$. Рассмотрим некоторый его подсписок $a_l,a_{l+1},a_{l+2},...,a_r$, где $1\le l \le r \le n$, и для каждого натурального числа $s$ обозначим через $K_s$ число юнг с ростом $s$ в этом подсписке. Назовем мощностью подсписка сумму произведений $K_s \cdot K_s \cdot s$ по всем различным натуральным $s$. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.
Необходимо вычислить мощности каждого из $t$ заданных подсписков.

Формат входных данных

Первая строка содержит два целых числа $n$ и $t$ $(1 \le n, t \le 200000)$ — длина списка и количество запросов соответственно. Вторая строка содержит $n$ натуральных чисел $a_i$ $(1 \le a_i \le 10^{6})$ — рост юнг. Следующие $t$ строк содержат по два натуральных числа $l$ и $r$ $(1 \le l \le r \le n)$ — индексы левого и правого концов соответствующего подсписка.

Формат выходных данных

Выведите $t$ строк, где $i$-ая строка содержит единственное натуральное число — мощность подсписка $i$-го запроса

3 2 1 2 1 1 2 1 3
3 6
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7
20 20 20

Q: Инверсии на отрезке

Дана перестановка из $n$ элементов. Ответьте на m запросов про число инверсий для подотрезка перестановки от $l$ до $r$. Инверсией называется пара индексов $i, j$ такая, что $i \lt j$ и $a_i > a_j$ , где $a_i$ - это i-ый элемент перестановки.

Формат входных данных

В первой строке задано число $n$ $(1 \le n \le 10^{5})$. Во второй строке задана перестановка из $n$ элементов (элементы перестановки — попарно различные целые числа от 1 до $n$). В третьей строке задано число $m$ $(1 \le m \le 10^{5})$. В последующих $m$ строках содержится по два числа, $l$ и $r$, границы запроса $(1 \le l, r \le n)$.

Формат выходных данных

Выведите $m$ строк, ответы на данные запросы.

5 4 5 2 3 1 3 1 3 3 5 1 5
2 2 8
6 5 2 4 3 1 6 4 4 6 2 5 1 5 1 6
1 4 8 8

Мо на дереве

TBA

R: MEX на пути в дереве

Дано дерево, на каждом ребре которого написано неотрицательное целое число. Вам необходимо ответить на несколько запросов вида «для данных вершин $u$, $v$ назовите наименьшее неотрицательное целое число, которое не встречается среди чисел, написанных на ребрах на пути от $u$ до $v$».

Входные данные

Первая строка входных данных содержит два числа $n$ и $q$ ($1 \le n, q \le 3 * 10^5$), количество вершин и количество запросов. Следующие $n − 1$ строк содержат по три числа $u_i$ ,$v_i$, $x_i$ ($1 \le u_i, v_i \le n; 0 \le x_i \le 10^9$) которые описывают ребро дерева ($u_i$, $v_i$), на котором написано число $x_i$. Следующие $q$ строк содержат по паре чисел $a_j$, $b_j$, которая обозначает запрос на пути от $a_j$ до $b_j$

Выходные данные

Для каждого запроса выведите единственное число — минимальное неотрицательное число, которое не встречается на пути.

7 6 2 1 1 3 1 2 1 4 0 4 5 1 5 6 3 5 7 4 1 3 4 1 2 4 2 5 3 5 3 7
0 1 2 2 3 3

3Д Мо

TBA

S: Дима и массив

Диме не дарили массив $a$, состоящий из $n$ целых чисел на день рождения, он не покупал его, не находил на улице, а он у него просто есть и всегда был, и Диме не очень-то и интересно откуда. Дима не играет с массивом, не дарит его Пете, не режет на кусочки и не стремится его уничтожить. Дима просто выполняет операции двух видов со своим массивом:

  1. $?$ $l$ $r$ — узнать MEX мультимножества $\{a_l, a_{l+1}, . . . , a_r\}$
  2. $!$ $i$ $x$ — присвоить $a_i$ значение $x$ $(0 \le x \le n)$

MEX мультимножества чисел $\{a_1, a_2, . . . , a_k\}$ — это минимальное целое $t \ge 0$ такое, что $t \ne a_i$ для всех $1 \le i \le k$.

На самом деле, Диме не очень нравится выполнять операции двух видов со своим массивом. Диму волнуют лишь результаты операций первого типа. Помогите Диме и напишите программу, которая выполнит операции за него.

Формат входных данных

Первая строка содержит два целых числа $n$ и $q$ $(1 \le n \le 500\,000, 1 \le q \le 250\,000)$ — размер массива, который есть у Димы и количество операций, соответственно. Вторая строка содержит $n$ целых чисел $a_i$ $(0 \le a_i \le n)$ — массив Димы до начала операций. Каждая из следующих $q$ строк содержит описание одной операции в формате, описанном выше. Элементы массива пронумерованы, начиная с 1.

Формат выходных данных

Для каждой операцияя первого типа выведите одно целое число — MEX соответствующего мультимножества. Ответы на запросы выводите в порядке, в котором они заданы во входных данных.

6 8 4 1 0 2 2 3 ? 1 6 ? 4 6 ? 2 5 ? 2 6 ! 3 3 ? 1 6 ! 4 0 ? 1 6
5 0 3 4 0 5

T: Машинное обучение

На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из n чисел. В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число $b1$ встречается $k1$ раз, $b_2$ - $k_2$ раз, и т.д. Тогда равномерностью массива называется такое минимальное целое число $c \ge 1$, что $c \ne k_i$ для любого $i$. В рамках вашего исследования вы хотите последовательно проделать $q$ операций.

Операция $t_i = 1$, $l_i$, $r_i$ задаёт запрос исследования. Необходимо вывести равномерность массива, состоящего из элементов на позициях от $l_i$ до $r_i$ включительно.

Операция $t_i = 2$, $p_i$, $x_i$ задаёт запрос уточнения данных. Начиная с этого момента времени $p_i$-му элементу массива присваивается значения $x_i$.

Входные данные

Первая строка содержит $n$ и $q$ — размер массива и число запросов соответственно. Во второй строке записаны ровно $n$ чисел — $a_1, a_2, ..., a_n$ ($1 \le a_i \le 10^9$). Каждая из оставшихся $q$ строк задаёт очередной запрос. Запрос первого типа задаётся тремя числами $t_i = 1$, $l_i$, $r_i$, где $1 \le  l_i \le r_i \le n$ — границы соответствующего отрезка. Запрос второго типа задаётся тремя числами $t_i = 2$, $p_i$, $x_i$, где $1 \le  p_i  \le  n$ — позиция в которой нужно заменить число, а $1 \le  x_i  \le 10^9$ — его новое значение

Выходные данные

Для каждого запроса первого типа выведите одно число — равномерность соответствующего отрезка массива.

10 4 1 2 3 1 1 2 2 2 9 9 1 1 1 1 2 8 2 7 1 1 2 8
2 3 2