Codeforces Round 807 (Div. 2) |
---|
Закончено |
После просмотра одного аниме перед сном Марку снится, что он стоит в старом классе с меловой доской, на которой записана последовательность из $$$n$$$ положительных целых чисел $$$a_1, a_2,\dots,a_n$$$.
Затем в класс заходит профессор Коро. Он может выполнять следующую операцию:
После чего профессор Коро задает марку вопрос: «Какое максимально возможное число может появиться на доске после некоторого количества таких операций?»
Марк быстро отвечает на этот вопрос, но он всё ещё медленнее профессора Коро. Поэтому профессор Коро решает задать Марку дополнительные вопросы. Он будет менять изначальную последовательность чисел на доске $$$q$$$ раз. Каждый раз он будет выбирать положительные целые числа $$$k$$$ и $$$l$$$, затем менять $$$a_k$$$ на $$$l$$$. После каждого такого изменения он будет спрашивать у Марка ответ на тот же самый вопрос.
Помогите Марку ответить на вопросы быстрее профессора Коро!
Обратите внимание, что изменения начальной последовательности на доске сохраняются. Изменения, внесенные в последовательность $$$a$$$, будут так же применяться при обработке следующих изменений.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2\leq n\leq 2\cdot 10^5$$$, $$$1\leq q\leq 2\cdot 10^5$$$) — длина последовательности $$$a$$$ и количество изменений соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1\leq a_i\leq 2\cdot 10^5$$$).
Затем следуют $$$q$$$ строк, каждая из которых содержит два целых числа $$$k$$$ и $$$l$$$ ($$$1\leq k\leq n$$$, $$$1\leq l\leq 2\cdot 10^5$$$), означающие изменение $$$a_k$$$ на значение $$$l$$$.
Выведите $$$q$$$ строк, $$$i$$$-я строка должна содержать единственное целое число — ответ после $$$i$$$-го изменения.
5 4 2 2 2 4 5 2 3 5 3 4 1 1 4
6 5 4 5
2 1 200000 1 2 200000
200001
В первом примере программа должна обработать $$$4$$$ изменения.
После первого обновления последовательность на доске выглядит как $$$[2,3,2,4,5]$$$. Одна из возможных последовательностей операций, достигающих числа $$$6$$$, такая:
Затем, во время второго изменения, массив станет равным $$$[2,3,2,4,3]$$$. В этот раз Марк не может достичь числа $$$6$$$. Однако одна из последовательностей операций, приводящая к числу $$$5$$$, такая:
Во время третьего изменения массив станет равным $$$[2,3,2,1,3]$$$. Один из возможных вариантов достичь числа $$$4$$$ такой:
Название |
---|