分数: 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