Codeforces Round 814 (Div. 1) |
---|
Закончено |
Тоне на день рождения подарили массив $$$a$$$ длины $$$n$$$, записанный на открытке. По какой-то причине открытка оказалась циклическим массивом, поэтому индекс элемента, находящегося строго справа от $$$n$$$-го, равен $$$1$$$. Тоня захотел получше изучить её, поэтому он купил робота «Бурёнка-179».
Программа для «Бурёнки» задается парой чисел $$$(s, k)$$$, $$$1 \leq s \leq n$$$, $$$1 \leq k \leq n-1$$$. Обратите внимание, что $$$k$$$ не может быть равно $$$n$$$. Изначально Тоня ставит робота в позицию $$$s$$$ массива. После этого «Бурёнка» сделает ровно $$$n$$$ шагов по массиву. Если в начале очередного шага «Бурёнка» стоит в позиции $$$i$$$, то происходит следующее:
Помогите Тоне найти максимальную возможную полезность программы для «Бурёнки», если изначальная полезность любой программы равна $$$0$$$.
Кроме того, друг Тони Илюша $$$q$$$ раз просит изменить массив. Каждое изменение состоит в присваивании $$$a_p := x$$$ для некоторых чисел $$$p$$$ и $$$x$$$. Вам необходимо найти максимальную возможную полезность программы после каждого из таких изменений.
В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержится два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).
Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива.
В следующих $$$q$$$ строках находятся описания изменений, каждое из которых состоит из двух целых чисел $$$p$$$ и $$$x$$$ ($$$1 \leq p \leq n$$$, $$$1 \leq x \leq 10^9$$$), означающих, что необходимо выполнить $$$a_p := x$$$.
Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем тестам не превосходят $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$q+1$$$ число — максимальную полезность программы изначально и после каждого запроса.
42 11 21 34 44 1 3 22 64 61 13 119 31 7 9 4 5 2 3 6 83 12 19 16 31 1 1 1 1 11 54 43 8
3 5 14 16 24 24 24 57 54 36 36 6 18 27 28
В первом наборе входных данных изначально и после каждого запроса ответ достигается при $$$s = 1$$$, $$$k = 1$$$ или $$$s = 2$$$, $$$k = 1$$$.
Во втором наборе входных данных изначально ответ достигается при $$$s = 1$$$, $$$k = 2$$$ или $$$s = 3$$$, $$$k = 2$$$. После первого запроса ответ достигается при $$$s = 2$$$, $$$k = 2$$$ или $$$s = 4$$$, $$$k = 2$$$.
Название |
---|