Задача №111798. Zeroes
Злобный учитель в MШП любит мучить детей сложными задачками. А если дети эти задачки не решают, учитель подвергает их самым жестоким наказаниям. На этот раз он придумал такую задачу:
Рейтинг всех учеников МШП записан в массив A
Запросы учителя таковы:
- Изменить рейтинг i-го ученика на число x
- Найти максимальную последовательность подряд идущих нулей (бесперспективных учеников) в массиве A на отрезке [l, r].
Помогите бедным ученикам МШП избежать зверского наказания за нерешение задачи на этот раз.
В первой строке входного файла записано число N (1 ≤ N ≤ 500000) – количество учеников в МШП. Во второй строке записано N чисел – их рейтинги, числа по модулю не превосходящие 1000 (по количеству задач, которые ученик решил или не решил за время обучения). В третьей строке записано число M (1 ≤ M ≤ 50000) – количество запросов. Каждая из следующих M строк содержит описания запросов:
UPDATE i x – обновить i-ый элемент массива значением x (1 ≤ i ≤ N, |x| ≤ 1000)
QUERY l r – найти длину максимальной последовательности из нулей на отрезке с l по r. (1 ≤ l ≤ r ≤ N)
В выходной файл выведите ответы на запросы QUERY в том же порядке, что и во входном файле
5 328 0 0 0 0 5 QUERY 1 3 UPDATE 2 832 QUERY 3 3 QUERY 2 3 UPDATE 2 0
2 1 1