| Условие задачи | | |
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 33700: Суммы на подотрезках
Темы:
Дерево отрезков, RSQ, RMQ
Реализуйте структуру данных для эффективного вычисления сумм подряд идущих элементов массива.
Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление суммы.
В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).'
Выходные данные
Для каждого запроса выведите сумму чисел соответствующего участка массива. Числа выводите в одну строку через пробел.
| Ввод |
Вывод |
5
4 4 8 7 8
2
1 2
1 3 |
8 16 |
| |
![]()
|
ID 33701:
Темы:
Дерево отрезков, RSQ, RMQ
Реализуйте эффективную структуру данных, позволяющую изменять элементы массивы и вычислять НОД нескольких подряд идущих элементов.
Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.
Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить НОД, u — обновить значение элемента).
Следом за s вводятся два числа — номера левой и правой границы отрезка.
Следом за u вводятся два числа — номер элемента и его новое значение.
Выходные данные
Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел.
| Ввод |
Вывод |
5
2 8 4 16 12
5
s 1 5
s 4 5
u 3 32
s 2 5
s 3 3 |
2 4 4 32 |
| |
![]()
|