← 返回题目列表

Codeforces · 1732/E

E. 位置

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

给定两个整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_n$$$。您需要处理以下两种类型的 $$$q$$$ 查询:

- $$$1$$$ $$$l$$$ $$$r$$$ $$$x$$$:为所有 $$$l \leq i \leq r$$$ 分配 $$$a_i := x$$$;
- $$$2$$$ $$$l$$$ $$$r$$$: 在所有$$$l \leq i \leq r$$$中找到以下表达式的最小值:$$$$$$\frac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}.$$$$$$

在此问题中,$$$\gcd(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数,$$$\operatorname{lcm}(x, y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最小公倍数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^4$$$) — 数组 $$$a$$$ 和 $$$b$$$ 中的数字数量以及查询数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^4$$$) — 数组 $$$a$$$ 的元素。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 5 \cdot 10^4$$$) — 数组 $$$b$$$ 的元素。

然后是 $$$q$$$ 行,其中 $$$j$$$-th 以整数 $$$t_j$$$ ($$$1 \leq t_j \leq 2$$$) 开头,表示第 $$$j$$$ 查询的类型为 $$$t_j$$$。

如果 $$$t_j = 1$$$,则后跟三个整数 $$$l_j$$$、$$$r_j$$$ 和 $$$x_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$、$$$1 \leq x_j \leq 5 \cdot 10^4$$$)。

如果 $$$t_j = 2$$$,则后面跟着两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$)。

保证至少有一个 $$$2$$$ 类型的查询。

输出

对于第二类的每个查询,输出表达式的最小值。

示例

输入 #1

10 10
6 10 15 4 9 25 2 3 5 30
1 2 3 4 6 9 12 15 18 30
2 1 10
1 7 10 9
2 5 10
1 1 6 14
2 4 7
2 3 9
1 2 9 30
2 1 4
2 3 7
2 5 10

输出 #1

1
2
12
2
10
5
2

输入 #2

4 4
10 2 12 5
1 12 16 1
2 2 4
1 2 3 18
1 2 2 10
2 2 3

输出 #2

5
30

注意

在第一个示例中:

- 对于第一个查询,我们可以选择 $$$i = 4$$$。所以值为 $$$\frac{\operatorname{lcm}(4, 4)}{\gcd(4, 4)} = \frac{4}{4} = 1$$$。
- 第二次查询后,数组 $$$a = [6, 10, 15, 4, 9, 25, 9, 9, 9, 9]$$$。
- 对于第三个查询,我们可以选择 $$$i = 9$$$。所以值为 $$$\frac{\operatorname{lcm}(9, 18)}{\gcd(9, 18)} = \frac{18}{9} = 2$$$。

第二个:

- 对于第一个查询,我们可以选择 $$$i = 4$$$。所以值为 $$$\frac{\operatorname{lcm}(1, 5)}{\gcd(1, 5)} = \frac{5}{1} = 5$$$。
- 第二次查询后,数组 $$$a = [10, 18, 18, 5]$$$。
- 第三次查询后,数组 $$$a = [10, 10, 18, 5]$$$。
- 对于第四个查询,我们可以选择 $$$i = 2$$$。所以值为 $$$\frac{\operatorname{lcm}(10, 12)}{\gcd(10, 12)} = \frac{60}{2} = 30$$$。