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

输入输出样例

输入样例 #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\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