AT_arc030_4.[ARC030D] グラフではない

有一个长度为 $N$ 的数列 $X = \{x_1, x_2, \ldots, x_N\}$。现在要对这个数列进行 $Q$ 次操作。操作有三种类型，具体如下：

• 1 a b v —— 将数列 $X$ 的区间 $[a, b]$ 上的每个元素都加上 $v$。
• 2 a b c d —— 将数列 $X$ 的区间 $[a, b]$ 的值替换为当前区间 $[c, d]$ 的值。保证 $b-a = d-c$。更严格地说，操作后得到的新数列 $X'$ 满足 $X'_{a} = X_c$，$X'_{a+1} = X_{c+1}$，……，$X'_{b} = X_{d}$。对于不在 $[a, b]$ 区间内的 $j$，有 $X'_j = X_j$。
• 3 a b —— 查询数列 $X$ 的区间 $[a, b]$ 上所有元素的和。

请你编写程序，依次处理这些操作。

输入通过标准输入给出，格式如下：

$N$ $Q$ $x_1$ $x_2$ … $x_N$ $Query_1$ $Query_2$ : $Query_Q$

• 第 $1$ 行包含两个整数，分别表示数列 $X$ 的长度 $N\ (1 \leq N \leq 2 \times 10^5)$ 和操作次数 $Q\ (1 \leq Q \leq 2 \times 10^5)$。
• 第 $2$ 行包含 $N$ 个整数，表示数列 $X$ 的每个元素 $x_i\ (-10^6 \leq x_i \leq 10^6)$，以空格分隔。
• 接下来的 $Q$ 行，每行一个操作，格式为 1 a b v、2 a b c d 或 3 a b。其中 $-10^6 \leq v \leq 10^6$，$1 \leq a \leq b \leq N$，$1 \leq c \leq d \leq N$，并保证 $b-a = d-c$。

对于每个 3 a b 形式的查询操作，按输入顺序输出答案。每个答案占一行。

样例解释 1

• 第 $1$ 个操作是查询 $[1,5]$ 区间的和，$1+2+3+4+5=15$，输出 $15$。
• 第 $2$ 个操作是将 $[1,3]$ 区间的每个元素加 $1$，操作后 $X = \{2,3,4,4,5\}$。
• 第 $3$ 个操作是查询 $[1,3]$ 区间的和，$2+3+4=9$，输出 $9$。
• 第 $4$ 个操作是将 $[2,4]$ 区间的值替换为 $[1,3]$ 区间的值，操作后 $X = \{3,4,4,4,5\}$。
• 第 $5$ 个操作是查询 $[1,5]$ 区间的和，$3+4+4+4+5=20$，输出 $20$。

由 ChatGPT 4.1 翻译