CF1942F.Farmer John's Favorite Function

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

ΩΩPARTS - Camellia

⠀

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$ 替换为 $x$ 。

输出格式

对于每次更新，输出一个整数 $\lfloor f(n) \rfloor$ ，每行一个。

输入输出样例

输入#1

输出#1

输入#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

输入#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

说明/提示

在第一个测试用例中，第一次更新后数组变为 $[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)\approx 1.732051$ ；
$f(2)\approx 3.966365$ ；
$f(3)\approx 1.991573$ ；
$f(4)\approx 2.998595$ ；
$f(5)\approx 2.999766$ 。

由于 $\lfloor f(5) \rfloor = 2$ ，所以输出 $2$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页