题目背景

HNOI2019 day2t3

题目描述

给定一个长度为 $n$ 的序列 $A_1,A_2,\dots, A_n$，以及 $m$ 个操作，每个操作将一个 $A_i$ 修改为 $k$。第一次修改之前及每次修改之后，都要求你找到一个同样长度为 $n$ 的单调不降序列 $B_1,B_2,\dots ,B_n$，使得 $\sum\limits_{i=1}^n(A_i-B_i)^2$ 最小，并输出最小值。

需要注意的是每次操作的影响都是独立的，也即每次操作只会对当前询问造成影响。

为了避免精度问题，我们保证这个最小值是个分数，也即能表示为两个非负整数相除的形式：$\dfrac{x}{y}$。那么你将要输出 $(x\times y^{P-2}\bmod P)$ 的值，表示模意义下 $\dfrac{x}{y}$ 的值。其中 $P=998244353$ 是一个大质数。

输入格式

第一行两个非负整数 $n,m$，代表序列长度和操作数。

第二行有 $n$ 个由空格隔开的正整数，代表序列 $A_1\sim A_n$。

接下来 $m$ 行每行两个正整数 $i,k$，代表将 $A_i$ 修改为 $k$。

输出格式

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

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

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\le 10^3$，且存在一种最优方案，使得 $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$。