Дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ и целое число $$$k$$$. А также $$$q$$$ запросов изменения массива: заменить $$$i$$$-й элемент массива $$$a$$$ на $$$x$$$.
После каждого запроса, а также для исходного массива, нужно сказать, чему равно максимальное значение $$$a_i + a_j$$$, где $$$1 \leq i \lt j \leq n$$$, $$$j - i \lt k$$$, а также сколько таких пар $$$(i, j)$$$, дающих максимальное значение, существует.
Обратите внимание, что в этой задаче необходимо отвечать на запросы в «онлайне».
В первой строке записаны два числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq n$$$).
Во второй строке записаны $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
В третьей строке записано единственное число $$$q$$$ ($$$1 \leq q \leq 10^5$$$). Затем в следующих $$$q$$$ строк идет описание запросов изменения.
На каждый запрос вводится два числа $$$i$$$ и $$$x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^9$$$) и пусть ответ для предыдущего запроса $$$(\textrm{mx}, \textrm{cnt})$$$, где $$$\textrm{mx}$$$ — максимальная сумма, а $$$\textrm{cnt}$$$ — сколько таких пар было. Тогда нужно будет изменить значение элемента $$$((i + \textrm{mx} + \textrm{cnt}) \bmod n) + 1$$$ на значение $$$x$$$.
Перед всеми изменениями и после каждого запроса выведите два числа в одной строке — какая максимальная сумма может получиться и сколько таких пар.
5 35 1 1 1 541 54 21 63 2
6 4 10 1 7 1 7 3 8 1
| BSUIR Open XIII: Школьный финал |
|---|
| Закончено |
