#21. Range Minimum Query (Segment Tree)
Sizga n ta butun sondan iborat A massiv beriladi. Dastur ishlashi davomida siz quyidagi ikki turdagi q ta so'rovga tezkorlik bilan javob berishingiz talab etiladi:
1 l r — Massivning l-indeksidan r-indeksigacha (ikkalasi ham kiradi) bo'lgan oraliqdagi eng kichik elementni toping va ekranga chiqaring.
2 i x — Massivning i-indeksida joylashgan element qiymatini x ga o'zgartiring (A[i] = x).
Birinchi qatorda ikkita butun son: n (massiv elementlari soni) va q (so'rovlar soni) beriladi. Ikkinchi qatorda n ta butun son — A massiv elementlari kiritiladi. Keyingi q ta qatorda yuqorida ko'rsatilgan formatdagi so'rovlar beriladi. Barcha indekslar 1 dan boshlanadi.
Har bir 1-tur so'rovi uchun alohida qatorda oraliqdagi eng kichik sonni chiqaring.
1 ≤ n, q ≤ 2×10⁵
You are given an array A consisting of n integers. During the program's execution, you need to quickly answer q queries of two types:
1 l r — Find and output the minimum element in the range from the l-th to the r-th index (inclusive).
2 i x — Update the value of the element at the i-th index to x (A[i] = x).
The first line contains two integers: n (number of elements) and q (number of queries). The second line contains n integers — the elements of array A. The next q lines contain queries in the format described above. All indices are 1-based.
For each query of the 1st type, output the minimum number in the range on a new line.
1 ≤ n, q ≤ 2×10⁵
Вам дан массив A, состоящий из n целых чисел. В процессе выполнения программы вам необходимо быстро отвечать на q запросов двух типов:
1 l r — Найти и вывести минимальный элемент на отрезке от l-го до r-го индекса (включительно).
2 i x — Изменить значение элемента по индексу i на x (A[i] = x).
В первой строке заданы два целых числа: n (количество элементов) и q (количество запросов). Во второй строке заданы n целых чисел — элементы массива A. В следующих q строках заданы запросы в описанном выше формате. Все индексы нумеруются с 1.
Для каждого запроса 1-го типа выведите минимальное число на отрезке в отдельной строке.
1 ≤ n, q ≤ 2×10⁵
Sizga n ta butun sondan iborat A massiv beriladi. Dastur ishlashi davomida siz quyidagi ikki turdagi q ta so'rovga tezkorlik bilan javob berishingiz talab etiladi:
1 l r — Massivning l-indeksidan r-indeksigacha (ikkalasi ham kiradi) bo'lgan oraliqdagi eng kichik elementni toping va ekranga chiqaring.
2 i x — Massivning i-indeksida joylashgan element qiymatini x ga o'zgartiring (A[i] = x).
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son: n (massiv elementlari soni) va q (so'rovlar soni) beriladi. Ikkinchi qatorda n ta butun son — A massiv elementlari kiritiladi. Keyingi q ta qatorda yuqorida ko'rsatilgan formatdagi so'rovlar beriladi. Barcha indekslar 1 dan boshlanadi.
Chiquvchi ma'lumotlar
Har bir 1-tur so'rovi uchun alohida qatorda oraliqdagi eng kichik sonni chiqaring.
Cheklovlar
1 ≤ n, q ≤ 2×10⁵
Misollar
3 2 5 2 3 1 1 3 2 2 10
2