分数: 450 点
问题陈述
有 N 连续单元格,已编号 1 to N.
对于每个 1 \leq i < N,细胞 i 和 i+1 相邻。
最初,细胞 i 涂有颜色 i.
你被给予 Q 查询。按顺序处理它们。每个查询属于以下两种类型之一。
1 x c: 重新绘制以下颜色 c:从单元格可到达的所有单元格 x 通过重复移动到与当前单元格颜色相同的相邻单元格。2 c:打印涂有颜色的单元格数量 c.
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 在第一种类型的查询中, 1 \leq x \leq N.
- 在第一类和第二类查询中, 1 \leq c \leq N.
- 至少有一个第二类型的查询。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
每个查询均以以下两种格式之一给出:
1 x c
2 c
输出
让 q 是第二类查询的数量。打印 q 行。
的 i- 第行应包含以下问题的答案 i-第一个这样的查询。
示例输入 1
5 6 1 5 4 1 4 2 2 2 1 3 2 1 2 3 2 3
示例输出 1
3 4
查询对单元格重新着色,如图所示。
