[HNOI2019] 序列

HNOI2019 day2t3

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

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

输出文件名为sequence.out。 输出$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 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$。 【编译命令】 对于 c++语言： g++ -o sequence sequence.cpp –lm –O2 对于 c 语言： gcc -o sequence sequence.c –lm –O2 对于 pascal 语言： fpc sequence.pas –O2