分数: 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