Запросы на максимум в диапазоне
Вам дан массив из
n элементов и q запросов. Существует два типа запросов:- Получить максимальное значение на указанном отрезке.
- Обновить элемент массива по заданной позиции.
Ваша задача — обрабатывать эти запросы эффективно.
Входные данные
Первая строка содержит два целых числа
n и q (1 ≤ n, q ≤ 100 000), которые обозначают количество элементов в массиве и количество запросов соответственно.Вторая строка содержит
n разделённых пробелами целых чисел (), которые образуют начальное состояние массива.Далее следует
q строк, каждая из которых описывает один запрос:- Для запросов на максимум в диапазоне: строка начинается с числа
1, за которым идут два целых числа и (), указывающие границы отрезка[], где нужно найти максимальное значение.
- Для запросов на обновление массива: строка начинается с числа
2, за которым следуют два целых числа и (), обозначающие позицию элемента для обновления и его новое значение.
Выходные данные
Для каждого запроса на максимум в диапазоне выведите в отдельной строке максимальное значение на указанном отрезке.
Примеры
Входные данные | Выходные данные |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 4
9
7 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB