E - Number of Blocks in an Interval Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、N 個のマスが横一列に並んだ塗り絵を管理している。マスには左から順に 1 番から N 番までの番号が付いている。

各マス i には色 C_i が塗られている。マスの列において、同じ色が連続するこれ以上延ばせない極大な区間のことを ブロック と呼ぶ。区間 [L, R] の ブロック数 とは、マスの列 C_L, C_{L+1}, \dots, C_R をブロックに分けたときのブロックの個数である。

例えば、列が 1, 1, 2, 2, 2, 1 であればブロックは (1, 1), (2, 2, 2), (1) の 3 つであり、ブロック数は 3 である。

青木君は以下の 2 種類の操作を合計 Q 回行う。各操作を順に処理し、問い合わせに答えよ。

  • 1 L R X ：区間 [L, R] のすべてのマスの色を X に変更する。
  • 2 L R ：現在の区間 [L, R] のブロック数を出力する。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq C_i \leq 10^9
  • 操作 1 L R X について、1 \leq L \leq R \leq N、1 \leq X \leq 10^9
  • 操作 2 L R について、1 \leq L \leq R \leq N
  • 入力はすべて整数である。

入力

N Q
C_1 C_2 \dots C_N
T_1
T_2
\vdots
T_Q
  • 1 行目には、マスの数 N と操作の回数 Q が、スペース区切りで与えられる。
  • 2 行目には、各マスの初期の色 C_1, C_2, \dots, C_N が、スペース区切りで与えられる。
  • 続く Q 行の i 行目には、i 番目の操作 T_i が与えられる。各操作は以下のいずれかの形式である。
  • 1 L R X：区間 [L, R] のすべてのマスの色を X に変更する。
  • 2 L R：現在の区間 [L, R] のブロック数を求める問い合わせ。

出力

操作 2 L R ごとに、その区間のブロック数を 1 行に 1 つずつ出力せよ。

入力例 1

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

出力例 1

3
2
1
3

入力例 2

5 7
4 5 5 4 4
2 1 5
1 2 4 4
2 1 5
2 3 3
1 1 1 7
2 1 2
2 4 5

出力例 2

3
1
1
2
1

入力例 3

12 12
1 2 2 3 3 3 2 2 4 4 5 1
2 1 12
2 3 10
1 2 5 2
2 1 8
1 9 12 2
2 1 12
1 6 6 7
2 5 7
1 1 12 3
2 1 12
1 4 9 1
2 1 12

出力例 3

7
4
4
4
3
1
3

入力例 4

20 18
1 1 2 3 3 4 4 4 5 6 6 7 8 8 9 9 9 10 1 1
2 1 20
2 4 17
1 3 8 3
2 1 10
1 10 15 8
2 8 18
1 1 2 2
2 1 5
1 16 20 8
2 10 20
1 5 5 2
2 1 20
1 6 14 1
2 1 20
2 6 14
1 1 20 7
2 1 20
2 11 11

出力例 4

11
7
4
5
2
1
6
5
1
1
1

入力例 5

1 5
1000000000
2 1 1
1 1 1 1
2 1 1
1 1 1 1000000000
2 1 1

出力例 5

1
1
1

Score : 466 pts

Problem Statement

Takahashi manages a coloring sheet consisting of N cells arranged in a horizontal row. The cells are numbered from 1 to N from left to right.

Each cell i is painted with color C_i. In a sequence of cells, a maximal consecutive interval of the same color that cannot be extended further is called a block. The number of blocks in an interval [L, R] is the number of blocks when the cell sequence C_L, C_{L+1}, \dots, C_R is divided into blocks.

For example, if the sequence is 1, 1, 2, 2, 2, 1, the blocks are (1, 1), (2, 2, 2), (1), giving 3 blocks, so the number of blocks is 3.

Aoki performs a total of Q operations of the following two types. Process each operation in order and answer the queries.

  • 1 L R X: Change the color of all cells in the interval [L, R] to X.
  • 2 L R: Output the number of blocks in the current interval [L, R].

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq C_i \leq 10^9
  • For operation 1 L R X: 1 \leq L \leq R \leq N, 1 \leq X \leq 10^9
  • For operation 2 L R: 1 \leq L \leq R \leq N
  • All input values are integers.

Input

N Q
C_1 C_2 \dots C_N
T_1
T_2
\vdots
T_Q
  • The first line contains the number of cells N and the number of operations Q, separated by a space.
  • The second line contains the initial colors of each cell C_1, C_2, \dots, C_N, separated by spaces.
  • The i-th of the following Q lines contains the i-th operation T_i. Each operation is in one of the following formats:
  • 1 L R X: Change the color of all cells in the interval [L, R] to X.
  • 2 L R: A query to find the number of blocks in the current interval [L, R].

Output

For each operation 2 L R, output the number of blocks in that interval, one per line.

Sample Input 1

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

Sample Output 1

3
2
1
3

Sample Input 2

5 7
4 5 5 4 4
2 1 5
1 2 4 4
2 1 5
2 3 3
1 1 1 7
2 1 2
2 4 5

Sample Output 2

3
1
1
2
1

Sample Input 3

12 12
1 2 2 3 3 3 2 2 4 4 5 1
2 1 12
2 3 10
1 2 5 2
2 1 8
1 9 12 2
2 1 12
1 6 6 7
2 5 7
1 1 12 3
2 1 12
1 4 9 1
2 1 12

Sample Output 3

7
4
4
4
3
1
3

Sample Input 4

20 18
1 1 2 3 3 4 4 4 5 6 6 7 8 8 9 9 9 10 1 1
2 1 20
2 4 17
1 3 8 3
2 1 10
1 10 15 8
2 8 18
1 1 2 2
2 1 5
1 16 20 8
2 10 20
1 5 5 2
2 1 20
1 6 14 1
2 1 20
2 6 14
1 1 20 7
2 1 20
2 11 11

Sample Output 4

11
7
4
5
2
1
6
5
1
1
1

Sample Input 5

1 5
1000000000
2 1 1
1 1 1 1
2 1 1
1 1 1 1000000000
2 1 1

Sample Output 5

1
1
1