P5294 [HNOI2019] 序列

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$ 行应为初始局面的答案。

### 【样例解释】 第一个询问的最优 $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$。