| Условие задачи | | Прогресс |
Темы:
sqrt декомпозиция
Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида l, r (\(1 <= l <= r <= n\)).
На каждый запрос нужно вывести сумму чисел на отрезке от l до r включительно. Элементы нумеруются с 1 до n.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 3 4
2
1 4
1 1
|
10
1 |
| 2 |
5
5 5 5 5 5
1
5 5
|
5 |
| |
![]()
|
|
Темы:
Дерево отрезков, RSQ, RMQ
sqrt декомпозиция
Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.
Входные данные
В первой строке вводится одно натуральное число N (\(1 <= N <= 100000\)) — количество чисел в массиве. Во второй строке вводятся N чисел от 1 до 100000 — элементы массива. В третьей строке вводится одно натуральное число K (\(1 <= K <= 30000\)) — количество запросов на вычисление максимума. В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).
Выходные данные
Для каждого запроса выведите значение максимального элемента на указанном отрезке массива. Числа выводите в одну строку через пробел.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
2 2 2 1 5
2
2 3
2 5 |
2 5 |
| |
![]()
|
|
Темы:
sqrt декомпозиция
Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).
Если \(t = 0\), то на запрос нужно вывести сумму чисел на отрезке от l до r включительно. Если \(t = 1\), то элементу с номером l присваивается значение r. Элементы нумеруются с 1 до n.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 2 3 4 5
4
0 1 2
1 1 5
0 1 2
0 1 1
|
3
7
5 |
| |
![]()
|
|
Темы:
sqrt декомпозиция
Дана матрица a размером \(n \cdot n\) (\(1 <= n <= 1000\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 1000\)) запросов вида x1, y1, x2, y2 (\(1 <= x_1 <= n\), \(1 <= y_1 <= n\), \(x_1 <= x_2 <= n\), \(y_1 <= y_2 <= n\)).
На каждый запрос нужно вывести максимальный элемент в подматрице с координатами краёв x1, y1 и x2, y2.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
1
1 1 3 4
|
6 |
| |
![]()
|
|
Темы:
sqrt декомпозиция
Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида *, l, r, k (\(1 <= l <= r <= n\), \(0 <= k <10\)) и запросов вида ?, i (\(1 <= i <= n\)).
В первом случае нужно умножить числа на отрезке от l до r включительно на k.
Во втором случае нужно вывести число, стоящее на позиции i.
Элементы нумеруются с 1 до n.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 1 1 1 1
3
? 3
* 2 3 9
? 3
|
1
9 |
| |
![]()
|
|
Темы:
sqrt декомпозиция
Дан массив a длины n (\(1 <= n <= 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида +, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)) и запросов вида ?, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)).
В первом случае нужно добавить к числам на отрезке от l до r включительно, число k.
Во втором случае нужно вывести 1, если на отрезке от l до r включительно, есть число k, иначе вывести 0.
Элементы нумеруются с 1 до n.
Гарантируется, что после любого запроса любой элемент массива a лежит в диапазоне от \(-10^9\) до \(10^9\) включительно.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 2 1 1 3
3
? 1 4 3
* 2 3 2
? 1 4 3
|
0
1 |
| |
![]()
|
|
Темы:
Дерево отрезков, RSQ, RMQ
sqrt декомпозиция
Хеш
Суффиксный массив
Динамическое программирование
Хеш
Скажем, что последовательность строк t1 , ..., tk является путешествием длины k , если для всех i > 1 ti является подстрокой ti - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.
Определим путешествие по строке s как путешествие t1 , ..., tk , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u1 , ..., uk + 1 , такие, что s = u1t1u2 t2 ... uk tk uk + 1 . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.
Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .
Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .
Во второй строке содержится строка s , состоящая из n строчных английских букв.
Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .
Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .
Во втором примере подходящим вариантом будет { bb , b } .
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
abcdbcc |
3 |
| 2 |
4
bbcb |
2 |
| |
![]()
|
|
Темы:
sqrt декомпозиция
На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из \(n\) чисел.
В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число \(b_1\) встречается \(k_1\) раз, \(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\) (\(1 \le n, q \le 100\,000\)) — размер массива и число запросов соответственно.
Во второй строке записаны ровно \(n\) чисел — \(a_1\), \(a_2\), \(\ldots\), \(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\) — его новое значение
Формат выходных данных
Для каждого запроса первого типа выведите одно число — равномерность соответствующего отрезка массива.
Примечание
Первый запрос состоит из ровно одного элемента — \(1\). Минимальное подходящее \(c = 2\).
Отрезок второго запроса состоит из четырёх \(2\), одной \(3\) и двух \(1\). Минимальное подходящее \(c = 3\).
Отрезок четвёртого запроса состоит из трёх \(1\), трёх \(2\) и одной \(3\). Минимальное подходящее \(c = 2\).
| |
![]()
|
|
Темы:
Динамическое программирование
sqrt декомпозиция
Костя и Женя — создатели группы <<Бумага>> — после выпуска легендарного альбома решили создать новое музыкальное объединение <<дневные грузчики>>, для этого им нужно найти двух новых людей.
Они пригласили на кастинг \(n\) человек. Кастинг продлится \(q\) дней. В \(i\)-й из дней Костя и Женя хотят найти двух человек на отрезке с \(l_i\) по \(r_i\), которые больше всего подходят их объединению. Так как <<дневные грузчики>> занимаются современным искусством, музыкальные навыки им не важны, и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.
Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!
Формат входных данных
В первой строке вам дано два числа \(n, q\) (\(2 \leqslant n \leqslant 4 \cdot 10^5, 1 \leqslant q \leqslant 10^6\)) — количество людей, которые пришли на кастинг, а также количество дней кастинга.
Во второй строке вам даны \(n\) чисел \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \leqslant a_i \leqslant n\)) — рост каждого из кандидатов.
Также гарантируется, что все \(a_i\) различны.
В следующих \(q\) строках даны по \(2\) числа \(l_i, r_i\) (\(1 \leqslant l_i < r_i \leqslant n\)) — отрезок людей для рассмотрения в \(i\)-й день кастинга.
Формат выходных данных
Выведите \(q\) строк. В \(i\)-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в \(i\)-й день кастинга.
Примечание
В первом примере минимальная разность на отрезке \([1, 2]\) составляет \(2\) (\(3 - 1 = 2\)), на отрезке \([2, 3]\) – \(1\), на отрезке \([1, 3]\) также \(1\).
В третьем примере минимальную разность на отрезке \([4, 6]\) составляют числа \(3, 5\) (\(5 - 3 = 2\)). На отрезке \([1, 2]\) минимальную разность имеют числа \(2, 6\) (\(6 - 2 = 0\)). На отрезке \([3, 6]\) минимальную разность имеют числа \(1, 3\) (\(3 - 1 = 2\)). На отрезке \([1, 3]\) минимальную разность образуют числа \(1, 2\) (\(2 - 1 = 1\)).
| |
![]()
|
|
Темы:
Дерево отрезков, RSQ, RMQ
sqrt декомпозиция
В холле 179 школы, есть информационный стенд размером H×W (H – высота, W – ширина). На этом стенде размещается информация о кружках, изменениях в расписании, победах в олимпиадах, а также другая важная информация.
Первого сентября стенд был пуст. Одно за другим на нем начали появляться объявления, которые потом не снимались.
Каждое объявление представляет собой полоску бумаги единичной высоты. I-ое объявление представляет собой прямоугольник размером 1×Wi.
Когда кто-либо вешает объявление на стенд, то он старается повесить объявление как можно выше. Среди возможных верхних мест всегда выбирается самое левое. Если подходящего места для объявления не нашлось, то объявление не вешается на стенд. Ваша задача состоит в том, чтобы для каждого объявления определить, как высоко оно будет располагаться (в каком ряду).
Входные данные
Первая строка содержит три целых числа H, W и N (1≤H,W≤109; 1≤N≤200000) — размеры стенда и количество объявлений. Каждая из следующих N строк содержит по одному целому числу Wi (1≤Wi≤109) — ширину i-го объявления.
Выходные данные
Для каждого из объявлений (в порядке следования во входном файле) выведите номер ряда, в котором оно будет размещено. Ряды занумерованы от 1 до H сверху вниз. Если объявление разместить нельзя — выведите «–1».
| |
![]()
|