問題文
长度 N 序列 有 X={x_1,x_2,...,x_N} 。在本专栏中 考虑执行 Q 查询操作。查询操作是3 有不同的类型,如下所示。
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 ≦ N ≦ 2×10^5) 和一个表示查询数量的整数 给出了 Q (1 ≦ Q ≦ 2×10^5) 。
- 2 编号顺序是 X 的 i 元素的值 x_i (-10^6 ≦ x_i ≦ 10^6) 以空格分隔 给出了 N 。
- 3 从行 Q 行,问题文本中解释的查询是
1 a b v,2 a b c d或 它以3 a b格式给出。-10^6 ≦ v ≦ 10^6,1 ≦ a ≦ b ≦ N,1 ≦ c ≦ d ≦ N,b-a = d-c得到保证。 对于
出力
3 a b 形式的查询,按给定顺序输出答案。向每个输出添加一个新行。
入力例1
5 5 1 2 3 4 5 3 1 5 1 1 3 1 3 1 3 2 1 3 2 4 3 1 5
出力例1
15 9 20
- 1 第二个查询是 这是一个输出[1,5] 之和的查询, 输出1+2+3+4+5=15 。
- 2 第二个查询是 这是一个输出[1,3] 统一 这是一个添加了 1 的查询,执行此操作后,X={2,3,4,4,5} 。 这是一个查找
- 3 第二个查询是 这是一个输出[1,3] 之和的查询,2+3+4=9 。
- 4 第二个查询是 这是一个输出[2,4] 的值 这是一个要复制到 [1,3] 的查询,执行此操作后, 给出了X={3,4,4,4,5} 。 这是一个查找
- 5 第二个查询是 这是一个输出[1,5] 之和的查询,3+4+4+4+5=20 。
入力例2
10 30 -5 -5 -2 -1 2 -2 0 -4 2 5 2 9 10 9 10 2 3 5 2 4 1 2 10 -1 2 1 7 1 7 3 1 4 2 1 6 2 7 2 5 8 6 9 3 4 8 3 1 10 3 9 9 1 3 8 -1 2 4 9 1 6 3 2 7 1 9 10 -4 1 6 9 -5 1 4 6 -7 3 2 5 2 10 10 7 7 1 3 4 -10 3 4 9 3 8 9 2 6 7 8 9 3 3 5 3 3 9 1 2 10 -10 2 4 6 4 6 2 4 9 5 10 1 2 6 7 3 7 8 1 3 6 3
出力例2
-20 -8 -18 1 -29 -36 -78 -18 -50 -86 -38