311158: CF1942F. Farmer John's Favorite Function
Description
Farmer John has an array $a$ of length $n$. He also has a function $f$ with the following recurrence:
- $f(1) = \sqrt{a_1}$;
- For all $i > 1$, $f(i) = \sqrt{f(i-1)+a_i}$.
Note that $f(i)$ is not necessarily an integer.
He plans to do $q$ updates to the array. Each update, he gives you two integers $k$ and $x$ and he wants you to set $a_k = x$. After each update, he wants to know $\lfloor f(n) \rfloor$, where $\lfloor t \rfloor$ denotes the value of $t$ rounded down to the nearest integer.
InputThe first line contains $n$ and $q$ ($1 \leq n, q \leq 2 \cdot 10^5$), the length of $a$ and the number of updates he will perform.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^{18}$).
The next $q$ lines each contain two integers $k$ and $x$ ($1 \leq k \leq n$, $0 \leq x \leq 10^{18}$), the index of the update and the element he will replace $a_k$ with.
OutputFor each update, output an integer, $\lfloor f(n) \rfloor$, on a new line.
ExamplesInput5 6 0 14 0 7 6 1 4 1 3 2 15 4 1 5 2 5 8Output
3 2 3 2 1 3Input
15 10 3364 1623 5435 7 6232 245 7903 3880 9738 577 4598 1868 1112 8066 199 14 4284 14 8066 6 92 6 245 2 925 2 1623 5 176 5 6232 3 1157 3 5435Output
16 17 16 17 16 17 16 17 16 17Input
2 2 386056082462833225 923951085408043421 1 386056082462833225 1 386056082462833224Output
961223744 961223743Input
13 10 31487697732100 446330174221392699 283918145228010533 619870471872432389 11918456891794188 247842810542459080 140542974216802552 698742782599365547 533363381213535498 92488084424940128 401887157851719898 128798321287952855 137376848358184069 3 283918145228010532 3 283918145228010533 1 2183728930312 13 1000000000000000000 10 1000000000000000000 9 1000000000000000000 8 1000000000000000000 7 1000000000000000000 6 1000000000000000000 5 1000000000000000000Output
370643829 370643830 370643829 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000Note
In the first test case, the array after the first update is $[4, 14, 0, 7, 6]$. The values of $f$ are:
- $f(1)=2$;
- $f(2)=4$;
- $f(3)=2$;
- $f(4)=3$;
- $f(5)=3$.
Since $\lfloor f(5) \rfloor = 3$, we output $3$.
The array after the second update is $[3, 14, 0, 7, 6]$. The values of $f$, rounded to $6$ decimal places, are:
- $f(1)\approx 1.732051$;
- $f(2)\approx 3.966365$;
- $f(3)\approx 1.991573$;
- $f(4)\approx 2.998595$;
- $f(5)\approx 2.999766$.
Since $\lfloor f(5) \rfloor = 2$, we output $2$.
Output
农民约翰有一个长度为 $ n $ 的数组 $ a $。他还有一个函数 $ f $,其递归定义为:
- $ f(1) = \sqrt{a_1} $
- 对于所有 $ i > 1 $,$ f(i) = \sqrt{f(i-1) + a_i} $
注意 $ 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 $,每个答案占一行。**题目大意:** 农民约翰有一个长度为 $ n $ 的数组 $ a $。他还有一个函数 $ f $,其递归定义为: - $ f(1) = \sqrt{a_1} $ - 对于所有 $ i > 1 $,$ f(i) = \sqrt{f(i-1) + a_i} $ 注意 $ 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 $,每个答案占一行。