P0068 区间计数
题目描述
维护一个长度为 n 的序列 {a1,a2,…,an},共有 m 次操作。操作共有 2 种:
∙赋值:将区间 [l,r] 中所有元素的值修改为 x;
∙询问:询问区间 [l,r] 中出现了多少种不同的数,同一个数出现多次只算一次。
保证所有数据随机生成。
输入格式
第一行输入两个整数 n,m(1≦n,m≦5×105) 代表序列长度与操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表序列的初始元素。
此后 m 行,每行输入一个操作。每行先输入一个整数 op(1≦op≦2) 代表操作类型,随后在同一行:
∙若 op=1,输入三个整数 $l, r, x \left(1 \leqq l \leqq r \leqq n;\ 1 \leqq x \leqq 10^9\right)$ 代表将区间 [l,r] 的值修改为 x;
∙若 op=2,输入两个整数 l,r(1≦l≦r≦n) 代表询问区间 [l,r] 中不同数的个数。
输出格式
对于每次操作 2,在一行上输出一个整数,代表区间 [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 解释
初始序列为 {1,2,3,4,5},操作过程如下:
∙执行 "2 1 5":区间 [1,5] 中有 1,2,3,4,5 共 5 种不同的数;
∙执行 "1 2 3 4":将区间 [2,3] 的值修改为 4,序列变为 {1,4,4,4,5};
∙执行 "2 1 5":区间 [1,5] 中有 1,4,5 共 3 种不同的数;
∙执行 "2 3 3":区间 [3,3] 中只有 4,共 1 种不同的数;
∙执行 "2 2 4":区间 [2,4] 中的数全为 4,共 1 种不同的数。
因此依次输出 5,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 解释
初始序列为 {5,5,2,9,5,1},操作过程如下:
∙执行 "2 1 6":区间 [1,6] 中有 1,2,5,9 共 4 种不同的数;
∙执行 "1 2 4 7":将区间 [2,4] 的值修改为 7,序列变为 {5,7,7,7,5,1};
∙执行 "2 1 6":区间 [1,6] 中有 1,5,7 共 3 种不同的数;
∙执行 "2 2 4":区间 [2,4] 中的数全为 7,共 1 种不同的数;
∙执行 "1 5 6 2":将区间 [5,6] 的值修改为 2,序列变为 {5,7,7,7,2,2};
∙执行 "2 1 6":区间 [1,6] 中有 2,5,7 共 3 种不同的数。
因此依次输出 4,3,1,3。
提示
对于全部数据,1≦n,m≦5×105,1≦ai,x≦109,1≦l≦r≦n。
保证所有数据随机生成。