[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