Comet OJ

C0810 [HNOI2019]序列

内存限制：512 MB 时间限制：2000 ms

题目描述

给定一个长度为 $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

5 3
9 2 4 6 4
1 1
1 4
5 6

样例输出 1

28
2
4
26

提示

【样例说明】

第一个询问的最优 $B$ 序列为：$\{5, 5, 5, 5, 5\}$。

第二个询问的最优 $B$ 序列为：$\{1, 2, 4, 5, 5\}$。

第三个询问的最优 $B$ 序列为：$\{3, 3, 4, 5, 5\}$。

第四个询问的最优 $B$ 序列为：$\{5, 5, 5, 6, 6\}$。

样例是存在最优方案使 $B_i$ 皆为整数的特殊情况。

【数据规模】

对于前 $10\%$ 的数据，保证 $n, m \le 10$，$k, A_i ≤ 1000$，且存在一种最优方案，使得 $B_i$ 皆为整数。

对于前 $30\%$ 的数据，保证 $n, m \le 100$。

对于另外 $20\%$ 的数据，保证 $m = 0$。

对于另外 $20\%$ 的数据，保证 $n, m \le 3 \times 10^4$。

对于所有数据，保证 $3 \le n \le 10^5， 0 \le m \le 10^5， 1 \le k, A_i \le 10^9$。