← 返回题目列表

AtCoder · arc030_4

D. 不是图表

中文机器翻译题面 查看原题

問題文

长度 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