E - Infinite Operations Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 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} を y_i に変更する。

クエリで数列が変更されるたびに、以下の問題の答えを \mod 998244353 で求めてください（注記参照）。

数列 A に対して以下の操作を n 回行うとき、獲得できる総得点の最大値を f(n) とする。

  • A_i\leq A_j となる i, j および A_i + 2x \leq A_j となる非負実数 x を選ぶ。
  • A_i に x を加え、A_j から x を引く。
  • x 点を獲得する。

極限 \displaystyle \lim_{n\to\infty} f(n) が存在することが証明できる。この値を求めよ。

注記

求める極限は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R\times Q\equiv P\pmod{998244353} かつ 0\leq R < 998244353 を満たす整数 R がただ一つ存在することが証明できます。この 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 行目には、i 番目のクエリで数列を変更した時点での、問題の答えを出力してください。

入力例 1

3 4
7 5 5
1 5
2 6
1 7
3 5

出力例 1

0
1
2
2

1 つめのクエリにより、数列は (5, 5, 5) へと変更されます。この場合任意の n に対して f(n) = 0 となり、答えは 0 となります。

2 つめのクエリにより、数列は (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 点を獲得する。

上の方法では 2 回の操作により 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

Score : 800 points

Problem Statement

Given are a sequence of N positive integers A = (A_1, A_2, \ldots, A_N) and Q queries. The i-th query is as follows:

  • given integers x_i and y_i (where 1\leq x_i\leq N), change A_{x_i} to y_i.

Each time the query changes the sequence, find the answer to the following problem modulo 998244353 (see Notes).

Let f(n) be the maximum total number of points when doing the following operation n times on A.

  • Choose i, j such that A_i\leq A_j and choose non-negative real number x such that A_i + 2x \leq A_j.
  • Add x to A_i and subtract x from A_j.
  • Gain x points.

It can be proved that the limit \displaystyle \lim_{n\to\infty} f(n) exists. Find this limit.

Notes

We can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as \frac{P}{Q} using two coprime integers P and Q, we can prove that there is a unique integer R such that R\times Q\equiv P\pmod{998244353} and 0\leq R < 998244353. Find this R.

Constraints

  • 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

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
x_1 y_1
\vdots
x_Q y_Q

Output

Print Q lines; the i-th line should contain the answer to the problem just after the change by the i-th query.

Sample Input 1

3 4
7 5 5
1 5
2 6
1 7
3 5

Sample Output 1

0
1
2
2

The first query changes the sequence to (5, 5, 5). Here, we have f(n) = 0 for any n, so the answer is 0.

The second query changes the sequence to (5, 6, 5). Here, one possible way to do the operations is as follows.

  • Choose (i,j,x) = (3,2,0.4), changing the sequence to (5, 5.6, 5.4) and gaining 0.4 points.
  • Choose (i,j,x) = (1,2,0.3), changing the sequence to (5.3, 5.3, 5.4) and gaining 0.3 points.

The above two operations gain 0.7 points, from which we can see that f(2) \geq 0.7.

We can prove that it is impossible to gain more than 1 point in total, and that the total number of points that can be gained by the optimal way to do the operations tends to 1 as the number of operations increases. Thus, we have \displaystyle \lim_{n\to\infty} f(n) = 1.

Sample Input 2

2 4
1 2
2 5
1 3
1 2
2 3

Sample Output 2

2
1
499122178
499122177