E - 1D Bucket Tool Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

1 から N の番号がついた N 個のマスが一列に並んでいます。
1 \leq i < N について、マス i とマス i+1 は隣接しています。

最初、マス i は色 i で塗られています。

クエリが Q 個与えられるので、順に処理してください。クエリは次の 2 種類のいずれかです。

  • 1 x c: マス x から始めて「いまいるマスと同じ色に塗られている隣接するマス」への移動を繰り返すことで到達可能なマスを全て色 c に塗り替える
  • 2 c: 色 c で塗られているマスの個数を答える

制約

  • 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 つ存在する
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

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

各クエリは以下の 2 種類のいずれかの形式で与えられる。

1 x c

2 c

出力

2 種類目のクエリの回数を 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

クエリにより、マスの色は図のように塗り替えられていきます。

図

Score : 450 points

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.

Figure