A5839 | $「HNOI2019」序列$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的序列 $A_1, \ldots , A_n$，以及 $m$ 个操作，每个操作将一个 $A_i$ 修改为 $k$。第一次修改之前及每次修改之后，都要求你找到一个同样长度为 $n$ 的单调不降序列 $B_1, \ldots , B_n$，使得 $\sum_{i=1}^n (A_i −B_i)^2$ 最小，并输出该最小值。需要注意的是每次操作的影响都是独立的，也即每次操作只会对当前询问造成影响。为了避免精度问题，我们保证这个最小值是个分数，也即能表示为两个非负整数相除的形式：$x/y$。那么你将要输出 $(x\times y^{P-2})\bmod P$ 的值，表示模意义下 $x/y$ 的值。其中 $P=998244353$ 是一个大质数。

第一行两个非负整数 $n,m$，代表序列长度和操作数。 第二行有 $n$ 个由空格隔开的正整数，代表序列 $A_1, \ldots , A_n$。 接下来 $m$ 行每行两个正整数 $i, k$，代表将 $A_i$ 修改为 $k$。

输出 $m + 1$ 行每行一个整数，第 $i$ 行输出第 $i - 1$ 次修改后的答案。特别的，第 $1$ 行应为初始局面的答案。

输入 #1

输出 #1

C++ 编辑器

输入

输出