--->
90 задач
<---
Источники
Реализуйте структуру данных для эффективного вычисления номера левого максимального из нескольких подряд идущих элементов массива.
В первой строке вводится одно натуральное число 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
Реализуйте структуру данных для эффективного вычисления значения максимального из нескольких подряд идущих элементов массива, а также количества элементов, равных максимальному на данном отрезке.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление максимума.
В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).
Для каждого запроса выведите в отдельной строке через пробел значение максимального элемента на указанном отрезке массива и количество максимальных элементов на этом отрезке.
5 2 2 2 1 5 2 2 3 2 5
2 2 5 1
Реализуйте структуру данных для эффективного вычисления количества нулей в отрезке массива.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление количества нулей.
В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).'
Для каждого запроса выведите количество нулей на соответствующем участке массива. Числа выводите в одну строку через пробел.
5 0 0 0 0 2 2 2 3 2 5
2 3
Реализуйте структуру данных для эффективного вычисления НОД нескольких подряд идущих элементов массива.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление НОД.
В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).'
Для каждого запроса выведите НОД всех чисел соответствующего участка массива. Числа выводите в одну строку через пробел.
5 2 2 2 1 5 2 2 3 2 5
2 1
Реализуйте эффективную структуру данных, позволяющую изменять элементы массива и вычислять максимальное значение из нескольких подряд идущих элементов.
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.
Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить максимум, u — обновить значение элемента).
Следом за s вводятся два числа — номера левой и правой границы отрезка.
Следом за u вводятся два числа — номер элемента и его новое значение.
Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел.
5 1 2 3 4 5 5 s 1 5 u 3 10 s 1 5 u 2 12 s 1 3
5 10 12