Олимпиадный тренинг

Задача . F. Любимая функция Фермера Джона


Задача

Темы: математика Перебор реализация Структуры данных *2700
ΩΩPARTS - Camellia
⠀

У Фермера Джона есть массив \(a\) длины \(n\). У него также есть функция \(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\) в отдельной строке.

Примечание

В первом примере массив после первого обновления имеет вид \([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\).


Примеры
№Входные данныеВыходные данные
1 5 6
0 14 0 7 6
1 4
1 3
2 15
4 1
5 2
5 8 
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 
16
17
16
17
16
17
16
17
16
17
3 2 2
386056082462833225 923951085408043421
1 386056082462833225
1 386056082462833224 
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 
370643829
370643830
370643829
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет