题目描述
给定一个长度为 n 的序列 A1,…,An,以及 m 个操作,每个操作将一个 Ai 修改为 k。第一次修改之前及每次修改之后,都要求你找到一个同样长度为 n 的单调不降序列 B1,…,Bn,使得 ∑i=1n(Ai−Bi)2 最小,并输出该最小值。需要注意的是每次操作的影响都是独立的,也即每次操作只会对当前询问造成影响。为了避免精度问题,我们保证这个最小值是个分数,也即能表示为两个非负整数相除的形式:x/y。那么你将要输出 (x×yP−2)modP 的值,表示模意义下 x/y 的值。其中 P=998244353 是一个大质数。
输入格式
第一行两个非负整数 n,m,代表序列长度和操作数。
第二行有 n 个由空格隔开的正整数,代表序列 A1,…,An。
接下来 m 行每行两个正整数 i,k,代表将 Ai 修改为 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}。
样例是存在最优方案使 Bi 皆为整数的特殊情况。
数据范围与提示
对于前 10% 的数据,保证 n,m≤10,k,Ai≤1000,且存在一种最优方案,使得 Bi 皆为整数。
对于前 30% 的数据,保证 n,m≤100。
对于另外 20% 的数据,保证 m=0。
对于另外 20% 的数据,保证 n,m≤3×104。
对于所有数据,保证 3≤n≤105,0≤m≤105,1≤k,Ai≤109。