10959. Zeroes
Злісний вчитель любить мучити дітей складними завданнями. А якщо діти ці завдання не вирішують, вчитель піддає їх найжорстокішим покаранням. Цього разу він придумав таке завдання:
Рейтинг всіх учнів записаний в масив \(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\),\(|х| ≤ 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
Коментарі
Ця задача є копією задачі 10593.
нехай уже буде так - там також є розвʼязки