AT_abc256_h [ABC256Ex] I like Query Problem

题目描述

给定 $N$、$Q$ 以及 $A = (a_1, a_2, \dots, a_N)$。
请处理 $Q$ 个如下所述的查询。查询有以下三种类型之一：

• 1 L R x ：将 $i = L, L+1, \dots, R$ 的 $a_i$ 更新为 $\left\lfloor \frac{a_i}{x} \right\rfloor$。
• 2 L R y ：将 $i = L, L+1, \dots, R$ 的 $a_i$ 更新为 $y$。
• 3 L R ：输出 $\sum_{i=L}^R a_i$。

输入格式

输入按如下格式从标准输入读入。其中 $\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$

输出格式

请按照题目要求，对每个查询类型为 $3$ 的查询，输出答案，每个答案占一行。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

说明/提示

数据范围

• $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$
• 输入的所有数均为整数

样例解释 1

初始时，$A = (2, 5, 6)$。因此，第 1 个查询的答案为 $a_1 + a_2 + a_3 = 2 + 5 + 6 = 13$。
第 2 个查询处理后，$A = (2, 2, 3)$。因此，第 3 个查询的答案为 $a_1 + a_2 = 2 + 2 = 4$。
第 4 个查询处理后，$A = (3, 3, 3)$。因此，第 5 个查询的答案为 $a_1 + a_2 + a_3 = 3 + 3 + 3 = 9$。

由 ChatGPT 4.1 翻译