В этом листке почти во всех задачах такой сюжет: есть массив данных, организованных в одномерный/двумерный массив или граф. И есть набор запросов, который предполагает вычисление некоторой функции на отрезке/прямоугольнике. В худшем случае возможно ещё и изменение данных.
Часто функция обладает таким полезным свойством: ответ множестве $X$ может быть легко вычислен на основе ответа на множестве $X\cup Y$ и на множестве $Y$. Если предпосчитать достаточно богатый набор значений функции, то потом можно быстро давать ответы.
Пример такой функции — сумма всех элементов множества.
Для подобный функций бывает полезно предпосчитать её значения на всех префиксах или всех суффиксах, или на всех подпрямоугольниках с вершиной в каком-нибудь угле данных.
Дан массив $A$ длины $N$, а также $M$ запросов вида $l$. Для каждого запроса найдите сумму первых $l$ элементов массива.
Дан массив $A$ длины $N$, а также $M$ запросов вида $l$ $r$. Нужно найди сумму элементов массива с $l$ по $r$
Дан массив $A$ длины $N$, а также $M$ запросов вида $l$ $r$. Нужно найди произведение элементов массива с $l$ по $r$ по модулю $10^9 + 7$. Гарантируется, что в массиве нет нулей.
Дан двумерный массив $A$ размера $N \times M$, а также $Q$ запросов вида $x\ y\ x_1\ y_1$. Нужно найди сумму элементов подмассива с левым верхним углом в $(x, y)$ и правым нижним $(x_1, y_1)$
Вообще, идея префиксных предподсчетов довольно часто возникает в программировании, но у данного подхода есть как плюсы (например, ответ за $O(1)$), так и минусы, например, изменение элементов происходит за $O(n)$, что очень долго. Научимся за не слишком медленно изменять элементы, не сильно замедлив процедуру ответа.
Идея несколько похожа на идею префиксного подсчета: давайте поделим весь массив на блоки размера $k$, в каждом из которых посчитаем ответ и запишем в массив $blocks$. Теперь научимся получать ответ. Пусть есть запрос на вычисление функции на отрезке с $l$ по $r$. Выделим внутри этого отрезка полные блоки, и добавим их в ответ, а "хвост" обработаем руками. Суммарная ассимптотика $O(n / k + k)$. Оказывается, самым оптимальным значением для $k$ есть $\sqrt n$
Теперь заметим, что изменение работает за $O(1)$. Изменив элемент и ответ в соответствующем блоке мы полностью обновим структуру.
Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:
Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:
Требуется ответить на все запросы произведения на отрезке. Гарантируется, что во всех версиях массива нет нулей
Дан массив $A$ длины $N$, а также $M$ запросов одного из 2х видов:
Требуется ответить на все запросы суммы на отрезке
Храни вспомогательный массив для блоков.
Давате хранить вспомогательный массив $add$ длиной $\sqrt n$ в каждой ячейке которого будем хранить насколько суммарно мы увеличили все числа в данном блоке. Теперь обновление выглядит так: ищем "цельные" блоки, увеличиваем суммарный инкремент, а "хвост" обрабатываем руками.
Часто, бывает удобно хранить вспомогательную структуру внутри декомпозиции, например, массив инкрементов на блоках. В следующих задачах вам предстоит самим догадаться, какие именно доп.структуры надо использовать.
Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа. Запрос первого типа – вычислить количество элементов массива на отрезке от l до r меньших заданного числа x. Запрос второго типа – увеличить все элементы массива на отрезке от l до r на заданное число x.
Требуется ответить на все запросы.
Для заданного массива требуется выполнить ряд запросов. Все запросы делятся на два типа.
В задачах на запросы на графах иногда работает следующий трюк: разделим вершины на "тяжелые" и "лёгкие" по следующему принципу: тяжелыми будут вершины со степенью больше или равные $\sqrt E$, а легкими все остальные. Тогда для тяжелых вершин будем хранить ответ явно, а для легких будем считать ответ "ручками". Так как тяжелых вершин не больше $\sqrt E$, и степень легких не больше $\sqrt E$, то суммарная ассимптотика решения - $\mathcal{O}(V\sqrt E)$
Вам дан граф с $N$ вершинами и $M$ ребрами. У каждой вершины есть свой цвет $v_i$. Вам дано $q$ запросов в виде пары $(v_i, c_i)$, означающий, что надо перекрасить вершину $v_i$ в цвет $c_i$. После каждого запроса нужно вывести количество ребер у которых вершины покрашены в разный цвет.
Дан неориентированный граф без петель и кратных ребер, у которого $n$ вершин и $m$ ребер. У каждой вершины есть цвет. Требуется ответить на $q$ запросов. Каждый запрос имеет один из двух типов:
Вам дан граф с $N$ вершинами и $M$ ребрами. Вам нужно найти количество циклов длины 3.
Дано число $n$ до $10^{12}$, посчитайте сумму $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor$
Назовем строку $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$ строк $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$
Некоторые запросы обновления можно легко обрабатывать группой, например сделав scanline, но тяжело обрабатывать по одному. В таких случаях можно откладывать их выполнение, и запоминать их в какой-нибудь список. При размере списка $\mathcal{O}(\sqrt{n})$ можно обработать все запросы этого списка группой. При выполнении get-запросов достаточно смотреть на все запросы внутри списка и смотреть, как они влияют на ответ
Малыш и Карлсон решили пойти на прогулку. Они знают, что прогулка будет совсем скучной, если перед ней не опустошить
несколько банок варенья.
Малыш достал из кладовки 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$, если
даже после выполнения всех этапов, в этой банке будет недостаточно варенья. Этапы нумеруются с единицы.
Пусть есть задача на массиве, которую, которую мы умеем решать без запросов обновления, в offline. Запросы могут быть любой степени ужасности, если мы умеем на них отвечать структурой данных, которая хранит информацию об отрезке $[l, r]$ и поддерживает следующие операции:
, которые меняют границы отрезка и внтуреннею структуру данных, а так же позволяют сделать запрос. Все запросы мы пересортируем по паре $(\lfloor \sqrt{l} \rfloor, r)$. Отвечать на запрос мы будем таким образом: с помощью реализованных операций изменим необходимые нам границы отрезка, после чего вызовем запрос query.
Заметим, что левые границы разбиваются по блокам, внутри блока правые границы отсортированы. При переходе от запроса к запросу, левая граница делает $\mathcal{O}(\sqrt{n})$ сдвигов. Правая же граница для запросов одного блока сделает суммарно не более $\mathcal{O}(n)$. Так как общее число блоков $\mathcal{O}(\sqrt{n})$, то и суммарное время работы составляет $\mathcal{O}(n\sqrt{n})$
Имеется список из $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$-го запроса
Дана перестановка из $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$ строк, ответы на данные запросы.
TBA
Дано дерево, на каждом ребре которого написано неотрицательное целое число. Вам необходимо ответить на несколько запросов вида «для данных вершин $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$
Для каждого запроса выведите единственное число — минимальное неотрицательное число, которое не встречается на пути.
TBA
Диме не дарили массив $a$, состоящий из $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 соответствующего мультимножества. Ответы на запросы выводите в порядке, в котором они заданы во входных данных.
На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из 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$ — его новое значение
Для каждого запроса первого типа выведите одно число — равномерность соответствующего отрезка массива.