Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

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

Дерево отрезков, RSQ, RMQ

Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление максимума.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

Выходные данные
Для каждого запроса выведите значение максимального элемента на указанном отрезке массива. Числа выводите в одну строку через пробел.
 

Ввод Вывод
5
2 2 2 1 5
2
2 3
2 5
2 5

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

Дерево отрезков, 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

Дерево отрезков, 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