AT_abc380_e.[ABC380E] 1D Bucket Tool

有 $N$ 个编号为 $1$ 到 $N$ 的格子排成一行。
对于 $1 \leq i < N$，格子 $i$ 和格子 $i+1$ 是相邻的。

最开始，第 $i$ 个格子被涂成颜色 $i$。

接下来有 $Q$ 个查询，请按顺序处理。每个查询有以下两种类型之一：

• 1 x c：从格子 $x$ 开始，不断移动到“与当前位置颜色相同的相邻格子”，将所有能够到达的格子全部涂成颜色 $c$。
• 2 c：询问当前被涂成颜色 $c$ 的格子的数量。

输入通过标准输入给出，格式如下：

$N$ $Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

每个查询有以下两种格式之一：

$1$ $x$ $c$

$2$ $c$

设第 $2$ 种查询的次数为 $q$，请输出 $q$ 行。
第 $i$ 行输出第 $i$ 次此类查询的答案。

数据范围

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• 对于第 $1$ 种查询，$1 \leq x \leq N$
• 对于第 $1,2$ 种查询，$1 \leq c \leq N$
• 至少存在一次第 $2$ 种查询
• 输入均为整数

样例说明 1

通过查询，格子的颜色会如图所示被不断涂色。

由 ChatGPT 4.1 翻译