← 返回题目列表

AtCoder · awc0063_e

E. 一个时间间隔内的块数

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

分数: 466 分

问题陈述

高桥管理着一张着色表,其中包括 N 单元格排列在水平行中。单元格编号为 1 to 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.

青木总共表演了 Q 操作有以下两种类型。按顺序处理每个操作并回答查询。

  • 1 L R X:更改间隔内所有单元格的颜色 [L, R] to 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
  • 第一行包含单元格数量 N 和操作次数 Q,用空格分隔。
  • 第二行包含每个单元格的初始颜色 C_1, C_2, \dots, C_N,用空格分隔。
  • 的 i- 以下各项 Q 行包含 i第次操作 T_i。每个操作都采用以下格式之一:
  • 1 L R X:更改间隔内所有单元格的颜色 [L, R] to X.
  • 2 L R:查询当前区间内的块数 [L, R].

输出

对于每个操作 2 L R,输出该区间内的块数,每行一个。


示例输入 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