P13983 数列分块入门 8
题目描述
给出一个长度为 n 的数列 {a1,a2,…,an},以及 n 次操作。每次操作给定 l,r,c,先统计区间 [l,r] 内有多少个元素等于 c,再把区间 [l,r] 内的所有元素都改为 c。
输入格式
第一行输入一个整数 n(1≦n≦3×105) 代表数列长度,同时代表操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(-2^{31} \leqq a_i \leqq 2^{31}-1\right)$ 代表数列的初始值。
此后 n 行,第 i 行输入三个整数 $l, r, c \left(1 \leqq l \leqq r \leqq n;\ -2^{31} \leqq c \leqq 2^{31}-1\right)$ 描述第 i 次操作。
输出格式
按操作顺序,每次操作新起一行输出一个整数,代表修改前区间 [l,r] 内等于 c 的元素个数。
测试样例
4
1 2 2 4
1 3 1
1 4 4
1 2 2
1 4 2
1
1
0
2
样例 1 解释
初始数列为 {1,2,2,4}。
∙第 1 次操作:区间 [1,3] 内等于 1 的元素有 1 个,随后把 [1,3] 都改为 1,数列变为 {1,1,1,4};
∙第 2 次操作:区间 [1,4] 内等于 4 的元素有 1 个,随后把 [1,4] 都改为 4,数列变为 {4,4,4,4};
∙第 3 次操作:区间 [1,2] 内等于 2 的元素有 0 个,随后把 [1,2] 都改为 2,数列变为 {2,2,4,4};
∙第 4 次操作:区间 [1,4] 内等于 2 的元素有 2 个,随后把 [1,4] 都改为 2,数列变为 {2,2,2,2}。
因此依次输出 1,1,0,2。
6
3 1 3 2 3 1
2 5 3
1 6 3
4 6 7
1 3 3
1 6 7
2 4 1
2
5
0
3
3
0
提示
洛谷的数列分块入门系列的测试数据范围与原题不同。
本题设有子任务:
∙子任务 1(40 分):1≦n≦105;
∙子任务 2(60 分):1≦n≦3×105。
对于所有数据,1≦n≦3×105,−231≦ai,c≦231−1,1≦l≦r≦n。