分数: 800 点
问题陈述
给出了一系列 N 正整数 A = (A_1, A_2, \ldots, A_N) 和 Q 查询。的 i第查询如下:
- 给定整数 x_i 和 y_i (其中 1\leq x_i\leq N),更改 A_{x_i} to y_i.
每次查询改变序列时,求以下问题的模数答案 998244353 (见注释)。
让 f(n) 是进行以下操作时的最大总点数 n 次 A.
- 选择 i, j 这样 A_i\leq A_j 并选择 非负实数 x 这样 A_i + 2x \leq A_j.
- 添加 x to A_i 并减去 x 来自 A_j.
- 增益 x 点。
可以证明极限 \displaystyle \lim_{n\to\infty} f(n) 存在。求这个极限。
注释
我们可以证明所讨论的极限始终是有理数。此外,在这个问题的约束下,当该数字表示为 \frac{P}{Q} 使用两个互质整数 P 和 Q,我们可以证明有一个唯一的整数 R 这样 R\times Q\equiv P\pmod{998244353} 和 0\leq R < 998244353。找到这个 R.
约束
- 2\leq N\leq 3\times 10^5
- 1\leq Q\leq 3\times 10^5
- 1\leq A_i \leq 10^9
- 1\leq x_i\leq N
- 1\leq y_i\leq 10^9
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 \ldots A_N x_1 y_1 \vdots x_Q y_Q
输出
打印 您选择的 Q 行;的 i-th 行应包含更改后问题的答案 i- 第一个查询。
示例输入 1
3 4 7 5 5 1 5 2 6 1 7 3 5
示例输出 1
0 1 2 2
第一个查询将序列更改为 (5, 5, 5)。在这里,我们有 f(n) = 0 对于任何 n,所以答案是 0.
第二个查询将序列更改为 (5, 6, 5)。这里,一种可能的操作方式如下。
- 选择 (i,j,x) = (3,2,0.4),将序列更改为 (5, 5.6, 5.4) 并获得 0.4 点。
- 选择 (i,j,x) = (1,2,0.3),将序列更改为 (5.3, 5.3, 5.4) 并获得 0.3 点。
以上两个操作增益 0.7 点,从中我们可以看到 f(2) \geq 0.7.
我们可以证明不可能获得超过 1 总点数,并且通过最佳操作方式可以获得的总点数往往是 1 随着操作次数的增加。因此,我们有 \displaystyle \lim_{n\to\infty} f(n) = 1.
示例输入 2
2 4 1 2 2 5 1 3 1 2 2 3
示例输出 2
2 1 499122178 499122177