Range Min-Max Query (Поиск минимума и максимума в диапазоне)
Вам дан массив из
n элементов и q запросов. Существует два типа запросов:- Найти минимальное и максимальное значения в указанном диапазоне.
- Обновить элемент массива по заданному индексу.
Ваша задача — эффективно обрабатывать эти запросы.
Входные данные
Первая строка входных данных содержит два целых числа
n и q (1 ≤ n, q ≤ 100 000), обозначающие количество элементов в массиве и число запросов соответственно.Вторая строка содержит
n целых чисел, разделённых пробелами (), — это начальные элементы массива.Следующие
q строк описывают запросы в одном из двух форматов:- Для запросов на поиск минимума и максимума в диапазоне: строка начинается с числа
1, за которым следуют два целых числа и (). Нужно вывести минимальное и максимальное значения в диапазоне[ $$l_i, r_i$$ ].
- Для запросов на обновление массива: строка начинается с числа
2, за которым следуют два целых числа и (). Нужно обновить элемент массива по индексу новым значением .
Выходные данные
Для каждого запроса на поиск минимума и максимума в диапазоне необходимо вывести два числа — минимальное и максимальное значения в выбранном участке массива, каждое на отдельной строке.
Пример
Входные данные | Выходные данные |
6 4
12 8 16 24 36 48
1 2 5
2 4 10
1 1 6
1 3 6 | 8 36
8 48
10 48 |
Constraints
Time limit: 0.9 seconds
Memory limit: 512 MB
Output limit: 1 MB