Farmer John's Favorite Function
Contest: CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2700
Tags: brute force, data structures, implementation, math

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.

Input format:
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.

Output format:
For each update, output an integer, $$$\lfloor f(n) \rfloor$$$, on a new line.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
5 6
0 14 0 7 6
1 4
1 3
2 15
4 1
5 2
5 8

Example output:
3
2
3
2
1
3

Example input:
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 5435

Example output:
16
17
16
17
16
17
16
17
16
17

Editorial:
Let's first look at the impact of earlier numbers on the final result. Earlier numbers can still influence $$$\lfloor f(n) \rfloor$$$ when $$$n$$$ is large. Suppose that all $$$f(i)$$$ are integers. Then decreasing any $$$a_i$$$ will decrease $$$\lfloor f(n) \rfloor$$$.
However, it is clear that the impact of earlier number on $$$\lfloor f(n) \rfloor$$$ is still extremely small. A key observation is that when $$$n \ge 6$$$, changing $$$a_1$$$ will only affect $$$\lfloor f(n) \rfloor$$$ by at most $$$1$$$.
Another observation is that we can take the floor each time we square root. Specifically, we can define $$$f$$$ as:
• $$$f(1) = \lfloor \sqrt{a_1} \rfloor$$$
• For all $$$i > 1$$$, $$$f(i) = \lfloor \sqrt{f(i-1)+a_i} \rfloor$$$
Let's divide our array into blocks of size $$$b=6$$$. We can append zeroes to the front of the array to make $$$n$$$ a multiple of $$$b$$$.
Consider some block representing range $$$[l,r]$$$. Let's consider the subarray $$$a_l,a_{l+1},\ldots ,a_r$$$. Let $$$v$$$ be the value of $$$f(r)$$$ if we let $$$f(l - 1)=0$$$. Using our first observation, we know that $$$f(r)$$$ will be either $$$v$$$ or $$$v+1$$$ depending on $$$f(l - 1)$$$. So let's find the smallest value $$$c$$$ such that if $$$f(l - 1)=c$$$, then $$$f(r)=v+1$$$. This can be done by iterating over the elements of the block backwards.
For each block, we store its corresponding ($$$c,v$$$). We can build a segment tree over the blocks for a $$$\mathcal{O}((n + q) \log n)$$$ solution.
Alternatively, we can do square root decomposition by having $$$b=\sqrt n$$$ which leads to a $$$\mathcal{O}(n + q \sqrt n)$$$ solution (in practice, we should set $$$b$$$ to something smaller like $$$100$$$).