← 返回题目列表

AtCoder · abc380_e

H. 一维铲斗工具

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

分数: 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

查询对单元格重新着色,如图所示。

Figure