分数: 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)。满足条件的茶壶的注水方式为零。