← 返回题目列表

Codeforces · 1942/F

F. 农夫约翰最喜欢的功能

中文机器翻译题面 查看原题

Farmer John 有一个长度为 $$$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$$$。

示例

输入 #1

5 6
0 14 0 7 6
1 4
1 3
2 15
4 1
5 2
5 8

输出 #1

3
2
3
2
1
3

输入 #2

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

输出 #2

16
17
16
17
16
17
16
17
16
17

输入 #3

2 2
386056082462833225 923951085408043421
1 386056082462833225
1 386056082462833224

输出 #3

961223744
961223743

输入#4

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 1000000000000000000

输出#4

370643829
370643830
370643829
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

注意

在第一个测试用例中,第一次更新后的数组是$$$[4, 14, 0, 7, 6]$$$。 $$$f$$$ 的值为:

- $$$f(1)=2$$$;
- $$$f(2)=4$$$;
- $$$f(3)=2$$$;
- $$$f(4)=3$$$;
- $$$f(5)=3$$$。

由于 $$$\lfloor f(5) \rfloor = 3$$$,我们输出 $$$3$$$。

第二次更新后的数组为$$$[3, 14, 0, 7, 6]$$$。 $$$f$$$ 的值四舍五入到 $$$6$$$ 小数位,如下:

- $$$f(1)\约 1.732051$$$;
- $$$f(2)\约 3.966365$$$;
- $$$f(3)\约 1.991573$$$;
- $$$f(4)\约 2.998595$$$;
- $$$f(5)\约 2.999766$$$。

由于 $$$\lfloor f(5) \rfloor = 2$$$,我们输出 $$$2$$$。