F. Farmer John's Favorite Function
brute force; data structures; implementation; math
ΩΩPARTS - Camellia⠀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.
The 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.
For each update, output an integer, \(\lfloor f(n) \rfloor\), on a new line.
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\).