| Условие задачи | | |
ID 29649: Сумма на отрезке - 1
Темы:
Корневая эвристика (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 |
| |
![]()
|
ID 33699: Максимумы на подотрезках
Темы:
Дерево отрезков, 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 |
| |
![]()
|
ID 29650: Сумма на отрезке - 2
Темы:
Корневая эвристика (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 |
| |
![]()
|
ID 29651: Максимум на матрице
Темы:
Корневая эвристика (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 |
| |
![]()
|
ID 29652: Умножение на отрезке
Темы:
Корневая эвристика (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 |
| |
![]()
|
ID 29653: Поиск числа на отрезке
Темы:
Корневая эвристика (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 |
| |
![]()
|
ID 38511: Путешествие по строке
Темы:
Дерево отрезков, 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 |
| |
![]()
|