[R42F]数组操作 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$。

你需要处理 $q$ 次操作，操作分为以下两种类型：

1. 1 l r x y：将区间 $[l, r]$ 内所有等于 $x$ 的数字修改为 $y$。
2. 2 l r：查询区间 $[l, r]$ 内所有数字的和。

格式

输入格式

第一行包含两个整数 $n, q$，分别表示数组长度和操作数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始的数组。

接下来 $q$ 行，每行描述一个操作：

• 若第一位为 1，则后面跟着四个整数 $l, r, x, y$，表示修改操作。
• 若第一位为 2，则后面跟着两个整数 $l, r$，表示查询操作。

输出格式

对于每个类型为 2 的查询操作，输出一行一个整数表示答案。

样例

样例输入 #1

6 4
1 2 1 2 1 2
1 1 6 1 3
2 1 6
1 1 6 2 3
2 1 6

样例输出 #1

15
18

样例解释 #1

• 初始数组：1 2 1 2 1 2。
• 操作 1 1 6 1 3：区间 $[1, 6]$ 内的 $1$ 变为 $3$。数组变为 3 2 3 2 3 2。
• 操作 2 1 6：求和 $3+2+3+2+3+2 = 15$。
• 操作 1 1 6 2 3：区间 $[1, 6]$ 内的 $2$ 变为 $3$。数组变为 3 3 3 3 3 3。
• 操作 2 1 6：求和 $3 \times 6 = 18$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n,q \le$	$a_i,x,y \le$	特殊性质
$1$	$10$	$1000$	$20$	无
$2$	$20$	$100000$	$2$
$3$	$10$		$20$	A
$4$	$20$			B
$5$	$40$			无

• 特殊性质 A：对于所有修改操作，保证 $r-l+1 \le 20$。
• 特殊性质 B：对于所有修改操作，保证 $r-l+1 \ge n-10$。

对于 $100\%$ 的数据：$1 \le n,q \le 10^5$，$1 \le l \le r \le n$，$1 \le a_i, x, y \le 20$。