← 返回题目列表

AtCoder · abc418_f

I. 我们是茶壶

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

分数: 550 点

问题陈述

有 N 茶壶排成一排,编号从 1 to N 从左到右。

有一个整数序列 (a_1, \dots, a_N),最初带有值 a_1 = \dots = a_N = -1.

您将在每个茶壶中倒入茶或咖啡,以满足以下条件:

  • 对于任何两个相邻的茶壶,其中至少有一个盛有茶。
  • 对于任何整数 i 满意 1 \leq i \leq N,如果 a_i \neq -1,那么正是 a_i 茶壶 1, \dots, i 含有咖啡。

你被给予 Q 查询,您应该按给定的顺序处理这些查询。

的 树的 j- 第一个查询 (1 \leq j \leq Q)如下:

  • 更改值 a_{X_j} to 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
  • 第一个查询操作后, a = (1,\ -1,\ -1,\ -1,\ -1)。满足条件的茶壶的注水方式有以下五种方式:
    • 将咖啡放入茶壶中 1,其他的还有茶。
    • 将咖啡放入茶壶中 1, 3,其他的还有茶。
    • 将咖啡放入茶壶中 1, 3, 5,其他的还有茶。
    • 将咖啡放入茶壶中 1, 4,其他的还有茶。
    • 将咖啡放入茶壶中 1, 5,其他的还有茶。
  • 第二个查询中的操作后, a = (1,\ -1,\ -1,\ 2,\ -1)。满足条件的茶壶的注水方式有以下三种:
    • 将咖啡放入茶壶中 1, 3,其他的还有茶。
    • 将咖啡放入茶壶中 1, 3, 5,其他的还有茶。
    • 将咖啡放入茶壶中 1, 4,其他的还有茶。
  • 第三次查询操作后, a = (0,\ -1,\ -1,\ 2,\ -1)。满足条件的茶壶的注水方式有以下一种:
    • 将咖啡放入茶壶中 2, 4,其他的还有茶。
  • 第四个查询操作后, a = (0,\ -1,\ -1,\ -1,\ -1)。满足条件的茶壶的注水方式有以下八种:
    • 不要将咖啡放入任何茶壶中,而将茶放入所有茶壶中。
    • 将咖啡放入茶壶中 2,其他的还有茶。
    • 将咖啡放入茶壶中 2, 4,其他的还有茶。
    • 将咖啡放入茶壶中 2, 5,其他的还有茶。
    • 将咖啡放入茶壶中 3,其他的还有茶。
    • 将咖啡放入茶壶中 3, 5,其他的还有茶。
    • 将咖啡放入茶壶中 4,其他的还有茶。
    • 将咖啡放入茶壶中 5,其他的还有茶。
  • 第五个查询操作后, a = (0,\ -1,\ -1,\ -1,\ 1)。满足条件的茶壶的注水方式有以下四种:
    • 将咖啡放入茶壶中 2,其他的还有茶。
    • 将咖啡放入茶壶中 3,其他的还有茶。
    • 将咖啡放入茶壶中 4,其他的还有茶。
    • 将咖啡放入茶壶中 5,其他的还有茶。
  • 第六个查询操作后, a = (0,\ -1,\ -1,\ -1,\ 5)。满足条件的茶壶的注水方式为零。