У Фермера Джона есть массив $$$a$$$ длины $$$n$$$. У него также есть функция $$$f$$$ со следующим рекуррентным соотношением:
Обратите внимание, что $$$f(i)$$$ не обязательно является целым числом.
Он планирует сделать $$$q$$$ обновлений массива. При каждом обновлении он дает вам два целых числа $$$k$$$ и $$$x$$$ и хочет, чтобы вы установили $$$a_k = x$$$. После каждого обновления он хочет узнать $$$\lfloor f(n) \rfloor$$$, где $$$\lfloor t \rfloor$$$ обозначает значение $$$t$$$, округленное вниз до ближайшего целого числа.
Первая строка содержит $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — длину $$$a$$$ и количество обновлений, которые он будет выполнять.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{18}$$$).
Следующие $$$q$$$ строк содержат по два целых числа $$$k$$$ и $$$x$$$ ($$$1 \leq k \leq n$$$, $$$0 \leq x \leq 10^{18}$$$) — индекс обновления и элемент, на который он заменит $$$a_k$$$.
После каждого обновления выведите целое число $$$\lfloor f(n) \rfloor$$$ в отдельной строке.
5 60 14 0 7 61 41 32 154 15 25 8
3 2 3 2 1 3
15 103364 1623 5435 7 6232 245 7903 3880 9738 577 4598 1868 1112 8066 19914 428414 80666 926 2452 9252 16235 1765 62323 11573 5435
16 17 16 17 16 17 16 17 16 17
2 2386056082462833225 9239510854080434211 3860560824628332251 386056082462833224
961223744 961223743
13 1031487697732100 446330174221392699 283918145228010533 619870471872432389 11918456891794188 247842810542459080 140542974216802552 698742782599365547 533363381213535498 92488084424940128 401887157851719898 128798321287952855 1373768483581840693 2839181452280105323 2839181452280105331 218372893031213 100000000000000000010 10000000000000000009 10000000000000000008 10000000000000000007 10000000000000000006 10000000000000000005 1000000000000000000
370643829 370643830 370643829 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
В первом примере массив после первого обновления имеет вид $$$[4, 14, 0, 7, 6]$$$. Значения $$$f$$$ следующие:
Поскольку $$$\lfloor f(5) \rfloor = 3$$$, ответом будет $$$3$$$.
Массив после второго обновления имеет вид $$$[3, 14, 0, 7, 6]$$$. Значения $$$f$$$, округленные до $$$6$$$ знаков после запятой, таковы:
Поскольку $$$\lfloor f(5) \rfloor = 2$$$, ответом будет $$$2$$$.
Название |
---|