103804: [Atcoder]ABC380 E - 1D Bucket Tool

Problem Statement

There are $N$ cells in a row, numbered $1$ to $N$.
For each $1 \leq i < N$, cells $i$ and $i+1$ are adjacent.

Initially, cell $i$ is painted with color $i$.

You are given $Q$ queries. Process them in order. Each query is of one of the following two types.

• 1 x c: Repaint the following to color $c$: all reachable cells reachable from cell $x$ by repeatedly moving to an adjacent cell painted in the same color as the current cell.
• 2 c: Print the number of cells painted with color $c$.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• In queries of the first type, $1 \leq x \leq N$.
• In queries of the first and second types, $1 \leq c \leq N$.
• There is at least one query of the second type.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Each query is given in one of the following two formats:

$1$ $x$ $c$

$2$ $c$

Output

Let $q$ be the number of queries of the second type. Print $q$ lines.

The $i$-th line should contain the answer to the $i$-th such query.

Sample Input 1

5 6
1 5 4
1 4 2
2 2
1 3 2
1 2 3
2 3

Sample Output 1

3
4

The queries recolor the cells as shown in the figure.

问题陈述

有一排N个单元格，编号从1到N。
对于每个1 ≤ 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

查询将单元格重新着色，如图中所示。