LG#P13983. 数列分块入门 8

数列分块入门 8

P13983 数列分块入门 8

题目描述

\hspace{15pt}给出一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},以及 nn 次操作。每次操作给定 l,r,cl, r, c,先统计区间 [l,r][l,r] 内有多少个元素等于 cc,再把区间 [l,r][l,r] 内的所有元素都改为 cc。

输入格式

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

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

\hspace{15pt}此后 nn 行,第 ii 行输入三个整数 $l, r, c \left(1 \leqq l \leqq r \leqq n;\ -2^{31} \leqq c \leqq 2^{31}-1\right)$ 描述第 ii 次操作。

输出格式

\hspace{15pt}按操作顺序,每次操作新起一行输出一个整数,代表修改前区间 [l,r][l,r] 内等于 cc 的元素个数。

测试样例

4
1 2 2 4
1 3 1
1 4 4
1 2 2
1 4 2
1
1
0
2

样例 1 解释

\hspace{15pt}初始数列为 {1,2,2,4}\{1,2,2,4\}。

∙ \hspace{23pt}\bullet\,第 11 次操作:区间 [1,3][1,3] 内等于 11 的元素有 11 个,随后把 [1,3][1,3] 都改为 11,数列变为 {1,1,1,4}\{1,1,1,4\};

∙ \hspace{23pt}\bullet\,第 22 次操作:区间 [1,4][1,4] 内等于 44 的元素有 11 个,随后把 [1,4][1,4] 都改为 44,数列变为 {4,4,4,4}\{4,4,4,4\};

∙ \hspace{23pt}\bullet\,第 33 次操作:区间 [1,2][1,2] 内等于 22 的元素有 00 个,随后把 [1,2][1,2] 都改为 22,数列变为 {2,2,4,4}\{2,2,4,4\};

∙ \hspace{23pt}\bullet\,第 44 次操作:区间 [1,4][1,4] 内等于 22 的元素有 22 个,随后把 [1,4][1,4] 都改为 22,数列变为 {2,2,2,2}\{2,2,2,2\}。

\hspace{15pt}因此依次输出 1,1,0,21,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

提示

\hspace{15pt}洛谷的数列分块入门系列的测试数据范围与原题不同。

\hspace{15pt}本题设有子任务:

∙ \hspace{23pt}\bullet\,子任务 11(4040 分):1≦n≦1051 \leqq n \leqq 10^5;

∙ \hspace{23pt}\bullet\,子任务 22(6060 分):1≦n≦3×1051 \leqq n \leqq 3 \times 10^5。

\hspace{15pt}对于所有数据,1≦n≦3×1051 \leqq n \leqq 3 \times 10^5,−231≦ai,c≦231−1-2^{31} \leqq a_i, c \leqq 2^{31}-1,1≦l≦r≦n1 \leqq l \leqq r \leqq n。