← 返回题目列表

AtCoder · abc256_h

Ex. 我喜欢查询问题

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

分数: 600 点

问题陈述

你被给予 N, Q,和 A=(a_1,\ldots,a_N).
流程 Q 查询如下所述。 每个查询属于以下三种类型之一:

  • 1 L R x:对于 i=L,L+1,\dots,R,更新值 a_i to \displaystyle \left\lfloor \frac{a_i}{x} \right\rfloor.
  • 2 L R y:对于 i=L,L+1,\dots,R,更新值 a_i to y.
  • 3 L R:打印 \displaystyle\sum_{i=L}^R a_i.

约束

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq L \leq R \leq N
  • 1 \leq a_i \leq 10^5
  • 2 \leq x \leq 10^5
  • 1 \leq y \leq 10^5
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出,其中 \text{query}_i 表示 i要处理的第一个查询:

N Q
a_1 a_2 \dots a_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

每个查询均以以下三种格式之一给出:

1 L R x
2 L R y
3 L R

输出

打印问题陈述中指定的查询答案,中间换行。


示例输入 1

3 5
2 5 6
3 1 3
1 2 3 2
3 1 2
2 1 2 3
3 1 3

示例输出 1

13
4
9

最初, A = (2, 5, 6)。 因此,问题的答案是 1-st 查询是 a_1 + a_2 + a_3 = 2 + 5 + 6 = 13.
当 2-nd 查询已处理, A = (2, 2, 3)。 因此,问题的答案是 3-rd 查询是 a_1 + a_2 = 2 + 2 = 4.
当 4第一个查询已被处理, A = (3, 3, 3)。 因此,问题的答案是 5-第一个查询是 a_1 + a_2 + a_3 = 3 + 3 + 3 = 9.


示例输入 2

6 11
10 3 5 20 6 7
3 1 6
1 2 4 3
3 1 3
2 1 4 10
3 3 6
1 3 6 2
2 1 4 5
3 1 6
2 1 3 100
1 2 5 6
3 1 4

示例输出 2

51
12
33
26
132