#3059. 「HNOI2019」序列

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

输入格式

第一行两个非负整数 n,m ,代表序列长度和操作数。

第二行有 n 个由空格隔开的正整数,代表序列 A_1, \ldots , A_n

接下来 m 行每行两个正整数 i, k ,代表将 A_i 修改为 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\}

样例是存在最优方案使 B_i 皆为整数的特殊情况。

数据范围与提示

对于前 10\% 的数据,保证 n, m \le 10 k, A_i ≤ 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