F - We're teapots Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

N 個のティーポットが横一列に並んでおり、左から順に 1 から N までの番号が付けられています。

整数列 (a_1, \dots, a_N) があり、はじめその値は a_1 = \dots = a_N = -1 です。

あなたは以下の条件をすべて満たすように、それぞれのティーポットに紅茶かコーヒーのいずれか 1 つを入れます。

  • どの隣り合う 2 つのティーポットについても、少なくとも片方には紅茶を入れる。
  • 1 \leq i \leq N を満たす整数 i について、a_i \neq -1 である場合、ティーポット 1, \dots, i のうちちょうど a_i 個にコーヒーを入れる。

クエリが Q 個与えられるので、与えられた順に処理してください。

j 番目のクエリ (1 \leq j \leq Q) は以下の通りです。

  • a_{X_j} の値を Y_j に変更する。その後、条件を満たすようなティーポットの満たし方の個数を 998244353 で割ったあまりを出力する。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq X_j \leq N (1 \leq j \leq Q)
  • -1 \leq Y_j \leq X_j (1 \leq j \leq Q)
  • 入力される値は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N Q
X_1 Y_1
\vdots
X_Q Y_Q

出力

Q 行出力せよ。

j 行目 (1 \leq j \leq Q) には、j 番目のクエリで出力するべき値を出力せよ。

入力例 1

5 6
1 1
4 2
1 0
4 -1
5 1
5 5

出力例 1

5
3
1
8
4
0
  • 1 番目のクエリでの操作後、a = (1,\ -1,\ -1,\ -1,\ -1) となります。条件を満たす入れ方は以下の 5 通りです。
    • ティーポット 1 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 1, 3 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 1, 3, 5 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 1, 4 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 1, 5 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
  • 2 番目のクエリでの操作後、a = (1,\ -1,\ -1,\ 2,\ -1) となります。条件を満たす入れ方は以下の 3 通りです。
    • ティーポット 1, 3 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 1, 3, 5 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 1, 4 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
  • 3 番目のクエリでの操作後、a = (0,\ -1,\ -1,\ 2,\ -1) となります。条件を満たす入れ方は以下の 1 通りです。
    • ティーポット 2, 4 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
  • 4 番目のクエリでの操作後、a = (0,\ -1,\ -1,\ -1,\ -1) となります。条件を満たす入れ方は以下の 8 通りです。
    • どのティーポットにもコーヒーを入れず、すべてのティーポットに紅茶を入れる。
    • ティーポット 2 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 2, 4 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 2, 5 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 3 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 3, 5 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 4 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 5 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
  • 5 番目のクエリでの操作後、a = (0,\ -1,\ -1,\ -1,\ 1) となります。条件を満たす入れ方は以下の 4 通りです。
    • ティーポット 2 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 3 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 4 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
    • ティーポット 5 にコーヒーを入れ、ほかのティーポットに紅茶を入れる。
  • 6 番目のクエリでの操作後、a = (0,\ -1,\ -1,\ -1,\ 5) となります。条件を満たす入れ方は 0 通りです。

Score : 550 points

Problem Statement

There are N teapots arranged in a row, numbered from 1 to N from left to right.

There is a sequence of integers (a_1, \dots, a_N), initially with values a_1 = \dots = a_N = -1.

You will fill each teapot with either tea or coffee so that the following conditions are all satisfied:

  • For any two adjacent teapots, at least one of them contains tea.
  • For any integer i satisfying 1 \leq i \leq N, if a_i \neq -1, then exactly a_i of teapots 1, \dots, i contain coffee.

You are given Q queries, which you should process in the given order.

The j-th query (1 \leq j \leq Q) is as follows:

  • Change the value of a_{X_j} to Y_j. Then, print the number, modulo 998244353, of ways to fill the teapots satisfying the conditions.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq X_j \leq N (1 \leq j \leq Q)
  • -1 \leq Y_j \leq X_j (1 \leq j \leq Q)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
X_1 Y_1
\vdots
X_Q Y_Q

Output

Print Q lines.

The j-th line (1 \leq j \leq Q) should contain the value to be printed for the j-th query.

Sample Input 1

5 6
1 1
4 2
1 0
4 -1
5 1
5 5

Sample Output 1

5
3
1
8
4
0
  • After the operation in the first query, a = (1,\ -1,\ -1,\ -1,\ -1). The ways to fill the teapots satisfying the conditions are the following five ways:
    • Put coffee in teapot 1, and tea in the others.
    • Put coffee in teapots 1, 3, and tea in the others.
    • Put coffee in teapots 1, 3, 5, and tea in the others.
    • Put coffee in teapots 1, 4, and tea in the others.
    • Put coffee in teapots 1, 5, and tea in the others.
  • After the operation in the second query, a = (1,\ -1,\ -1,\ 2,\ -1). The ways to fill the teapots satisfying the conditions are the following three ways:
    • Put coffee in teapots 1, 3, and tea in the others.
    • Put coffee in teapots 1, 3, 5, and tea in the others.
    • Put coffee in teapots 1, 4, and tea in the others.
  • After the operation in the third query, a = (0,\ -1,\ -1,\ 2,\ -1). The ways to fill the teapots satisfying the conditions are the following one way:
    • Put coffee in teapots 2, 4, and tea in the others.
  • After the operation in the fourth query, a = (0,\ -1,\ -1,\ -1,\ -1). The ways to fill the teapots satisfying the conditions are the following eight ways:
    • Put coffee in none of the teapots and tea in all of them.
    • Put coffee in teapot 2, and tea in the others.
    • Put coffee in teapots 2, 4, and tea in the others.
    • Put coffee in teapots 2, 5, and tea in the others.
    • Put coffee in teapot 3, and tea in the others.
    • Put coffee in teapots 3, 5, and tea in the others.
    • Put coffee in teapot 4, and tea in the others.
    • Put coffee in teapot 5, and tea in the others.
  • After the operation in the fifth query, a = (0,\ -1,\ -1,\ -1,\ 1). The ways to fill the teapots satisfying the conditions are the following four ways:
    • Put coffee in teapot 2, and tea in the others.
    • Put coffee in teapot 3, and tea in the others.
    • Put coffee in teapot 4, and tea in the others.
    • Put coffee in teapot 5, and tea in the others.
  • After the operation in the sixth query, a = (0,\ -1,\ -1,\ -1,\ 5). The number of ways to fill the teapots satisfying the conditions is zero.