← 返回题目列表

AtCoder · arc126_e

E. 无限操作

中文机器翻译题面 查看原题

分数: 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