#30. Lazy Propagation Segment Tree
Sizga n ta butun sondan iborat A massivi hamda q ta so'rov beriladi. Massiv ustida guruhli operatsiyalarni tezkor bajarishingiz kerak:
1 l r x — Massivning l-indeksdan to r-indeksgacha bo'lgan barcha elementlariga x qiymatini qo'shib chiqing (A[i] = A[i] + x, bu yerda l <= i <= r).
2 l r — Massivning l-indeksdan r-indeksgacha bo'lgan qismidagi eng katta elementni (maksimumni) toping va ekranga chiqaring.
Birinchi qatorda n va q sonlari. Ikkinchi qatorda n ta massiv elementi kiritiladi. Keyingi q ta qatorda yuqorida ko'rsatilgan ikki formatdan biridagi so'rovlar beriladi.
Har bir 2-tur so'rovi uchun joriy oraliqdagi maksimal qiymatni alohida qatorda chiqaring.
n ≤ 2×10⁵
You are given an array A consisting of n integers, and q queries. You need to perform group operations on the array quickly:
1 l r x — Add the value x to all elements of the array from the l-th index to the r-th index (A[i] = A[i] + x, where l <= i <= r).
2 l r — Find and output the largest element (maximum) in the subarray from the l-th index to the r-th index.
The first line contains the numbers n and q. The second line contains the n elements of the array. The next q lines contain queries in one of the two formats shown above.
For each query of type 2, output the maximum value in the current range on a new line.
n ≤ 2×10⁵
Вам дан массив A, состоящий из n целых чисел, и q запросов. Вам необходимо быстро выполнять групповые операции над массивом:
1 l r x — Прибавить значение x ко всем элементам массива от l-го до r-го индекса (A[i] = A[i] + x, где l <= i <= r).
2 l r — Найти и вывести наибольший элемент (максимум) в подмассиве от l-го до r-го индекса.
В первой строке заданы числа n и q. Во второй строке заданы n элементов массива. В следующих q строках заданы запросы в одном из двух указанных выше форматов.
Для каждого запроса 2-го типа выведите максимальное значение на текущем отрезке в отдельной строке.
n ≤ 2×10⁵
Sizga n ta butun sondan iborat A massivi hamda q ta so'rov beriladi. Massiv ustida guruhli operatsiyalarni tezkor bajarishingiz kerak:
1 l r x — Massivning l-indeksdan to r-indeksgacha bo'lgan barcha elementlariga x qiymatini qo'shib chiqing (A[i] = A[i] + x, bu yerda l <= i <= r).
2 l r — Massivning l-indeksdan r-indeksgacha bo'lgan qismidagi eng katta elementni (maksimumni) toping va ekranga chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda n va q sonlari. Ikkinchi qatorda n ta massiv elementi kiritiladi. Keyingi q ta qatorda yuqorida ko'rsatilgan ikki formatdan biridagi so'rovlar beriladi.
Chiquvchi ma'lumotlar
Har bir 2-tur so'rovi uchun joriy oraliqdagi maksimal qiymatni alohida qatorda chiqaring.
Cheklovlar
n ≤ 2×10⁵
Misollar
3 3 1 2 3 2 1 3 1 1 2 5 2 1 3
3 7