#P0068. 区间计数

区间计数

P0068 区间计数

题目描述

\hspace{15pt}维护一个长度为 nn 的序列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},共有 mm 次操作。操作共有 22 种:

∙ \hspace{23pt}\bullet\,赋值:将区间 [l,r][l, r] 中所有元素的值修改为 xx;

∙ \hspace{23pt}\bullet\,询问:询问区间 [l,r][l, r] 中出现了多少种不同的数,同一个数出现多次只算一次。

\hspace{15pt}保证所有数据随机生成。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦5×105)n, m \left(1 \leqq n, m \leqq 5 \times 10^5\right) 代表序列长度与操作次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表序列的初始元素。

\hspace{15pt}此后 mm 行,每行输入一个操作。每行先输入一个整数 op(1≦op≦2)op \left(1 \leqq op \leqq 2\right) 代表操作类型,随后在同一行:

∙ \hspace{23pt}\bullet\,若 op=1op = 1,输入三个整数 $l, r, x \left(1 \leqq l \leqq r \leqq n;\ 1 \leqq x \leqq 10^9\right)$ 代表将区间 [l,r][l, r] 的值修改为 xx;

∙ \hspace{23pt}\bullet\,若 op=2op = 2,输入两个整数 l,r(1≦l≦r≦n)l, r \left(1 \leqq l \leqq r \leqq n\right) 代表询问区间 [l,r][l, r] 中不同数的个数。

输出格式

\hspace{15pt}对于每次操作 22,在一行上输出一个整数,代表区间 [l,r][l, r] 中不同数的个数。

测试样例

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

样例 1 解释

\hspace{15pt}初始序列为 {1,2,3,4,5}\{1, 2, 3, 4, 5\},操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "2 1 5"\texttt{"2 1 5"}:区间 [1,5][1, 5] 中有 1,2,3,4,51, 2, 3, 4, 5 共 55 种不同的数;

∙ \hspace{23pt}\bullet\,执行 "1 2 3 4"\texttt{"1 2 3 4"}:将区间 [2,3][2, 3] 的值修改为 44,序列变为 {1,4,4,4,5}\{1, 4, 4, 4, 5\};

∙ \hspace{23pt}\bullet\,执行 "2 1 5"\texttt{"2 1 5"}:区间 [1,5][1, 5] 中有 1,4,51, 4, 5 共 33 种不同的数;

∙ \hspace{23pt}\bullet\,执行 "2 3 3"\texttt{"2 3 3"}:区间 [3,3][3, 3] 中只有 44,共 11 种不同的数;

∙ \hspace{23pt}\bullet\,执行 "2 2 4"\texttt{"2 2 4"}:区间 [2,4][2, 4] 中的数全为 44,共 11 种不同的数。

\hspace{15pt}因此依次输出 5,3,1,15, 3, 1, 1。

6 6
5 5 2 9 5 1
2 1 6
1 2 4 7
2 1 6
2 2 4
1 5 6 2
2 1 6
4
3
1
3

样例 2 解释

\hspace{15pt}初始序列为 {5,5,2,9,5,1}\{5, 5, 2, 9, 5, 1\},操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "2 1 6"\texttt{"2 1 6"}:区间 [1,6][1, 6] 中有 1,2,5,91, 2, 5, 9 共 44 种不同的数;

∙ \hspace{23pt}\bullet\,执行 "1 2 4 7"\texttt{"1 2 4 7"}:将区间 [2,4][2, 4] 的值修改为 77,序列变为 {5,7,7,7,5,1}\{5, 7, 7, 7, 5, 1\};

∙ \hspace{23pt}\bullet\,执行 "2 1 6"\texttt{"2 1 6"}:区间 [1,6][1, 6] 中有 1,5,71, 5, 7 共 33 种不同的数;

∙ \hspace{23pt}\bullet\,执行 "2 2 4"\texttt{"2 2 4"}:区间 [2,4][2, 4] 中的数全为 77,共 11 种不同的数;

∙ \hspace{23pt}\bullet\,执行 "1 5 6 2"\texttt{"1 5 6 2"}:将区间 [5,6][5, 6] 的值修改为 22,序列变为 {5,7,7,7,2,2}\{5, 7, 7, 7, 2, 2\};

∙ \hspace{23pt}\bullet\,执行 "2 1 6"\texttt{"2 1 6"}:区间 [1,6][1, 6] 中有 2,5,72, 5, 7 共 33 种不同的数。

\hspace{15pt}因此依次输出 4,3,1,34, 3, 1, 3。

提示

\hspace{15pt}对于全部数据,1≦n,m≦5×1051 \leqq n, m \leqq 5 \times 10^5,1≦ai,x≦1091 \leqq a_i, x \leqq 10^9,1≦l≦r≦n1 \leqq l \leqq r \leqq n。

\hspace{15pt}保证所有数据随机生成。