Location

题意翻译

初始给定序列 $a,b$，需要维护以下操作： 1. 给定 $l,r,x$，对于 $\forall i\in[l,r]$，令 $a_i=x$。 2. 给定 $l,r$，求 $\min_{i\in[l,r]}\frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}$。 数据范围 $1\leq n,q,a_i\leq 50000$。 Translater by Prean

题目描述

You are given two arrays of integers $ a_1, a_2, \ldots, a_n $ and $ b_1, b_2, \ldots, b_n $ . You need to handle $ q $ queries of the following two types: - $ 1 $ $ l $ $ r $ $ x $ : assign $ a_i := x $ for all $ l \leq i \leq r $ ; - $ 2 $ $ l $ $ r $ : find the minimum value of the following expression among all $ l \leq i \leq r $ : $ $\frac{\operatorname{lcm}(a_i, b_i)}{\gcd(a_i, b_i)}. $ $ </li></ul><p>In this problem $ \\gcd(x, y) $ denotes the <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest common divisor</a> of $ x $ and $ y $ , and $ \\operatorname{lcm}(x, y) $ denotes the <a href="https://en.wikipedia.org/wiki/Least_common_multiple">least common multiple</a> of $ x $ and $ y$.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \leq n, q \leq 5 \cdot 10^4 $ ) — the number of numbers in the arrays $ a $ and $ b $ and the number of queries. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 5 \cdot 10^4 $ ) — the elements of the array $ a $ . The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \leq b_i \leq 5 \cdot 10^4 $ ) — the elements of the array $ b $ . Then $ q $ lines follow, $ j $ -th of which starts with an integer $ t_j $ ( $ 1 \leq t_j \leq 2 $ ) and means that the $ j $ -th query has type $ t_j $ . If $ t_j = 1 $ , it is followed by three integers $ l_j $ , $ r_j $ , and $ x_j $ ( $ 1 \leq l_j \leq r_j \leq n $ , $ 1 \leq x_j \leq 5 \cdot 10^4 $ ). If $ t_j = 2 $ , it is followed by two integers $ l_j $ and $ r_j $ ( $ 1 \leq l_j \leq r_j \leq n $ ). It is guaranteed that there is at least one query of type $ 2 $ .

输出格式

For each query of the second type, output the minimum value of the expression.

输入输出样例

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

说明

In the first example: - For the first query we can choose $ i = 4 $ . So the value is $ \frac{\operatorname{lcm}(4, 4)}{\gcd(4, 4)} = \frac{4}{4} = 1 $ . - After the second query the array $ a = [6, 10, 15, 4, 9, 25, 9, 9, 9, 9] $ . - For the third query we can choose $ i = 9 $ . So the value is $ \frac{\operatorname{lcm}(9, 18)}{\gcd(9, 18)} = \frac{18}{9} = 2 $ . In the second: - For the first query we can choose $ i = 4 $ . So the value is $ \frac{\operatorname{lcm}(1, 5)}{\gcd(1, 5)} = \frac{5}{1} = 5 $ . - After the second query the array $ a = [10, 18, 18, 5] $ . - After the third query the array $ a = [10, 10, 18, 5] $ . - For the fourth query we can choose $ i = 2 $ . So the value is $ \frac{\operatorname{lcm}(10, 12)}{\gcd(10, 12)} = \frac{60}{2} = 30 $ .

**题意翻译**

初始给定序列 $a,b$，需要维护以下操作：

1. 给定 $l,r,x$，对于 $\forall i\in[l,r]$，令 $a_i=x$。
2. 给定 $l,r$，求 $\min_{i\in[l,r]}\frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}$。

数据范围 $1\leq n,q,a_i\leq 50000$。

**题目描述**

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

- $ 1 $ $ l $ $ r $ $ x $ : 将 $ a_i $ 的值赋为 $ x $ 对于所有 $ l \leq i \leq r $；
- $ 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 $ 行以整数 $ 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 $ 的查询。

**输出格式**

对于每个类型为 $ 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**题意翻译** 初始给定序列 $a,b$，需要维护以下操作： 1. 给定 $l,r,x$，对于 $\forall i\in[l,r]$，令 $a_i=x$。 2. 给定 $l,r$，求 $\min_{i\in[l,r]}\frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}$。 数据范围 $1\leq n,q,a_i\leq 50000$。 **题目描述** 给定两个整数数组 $ a_1, a_2, \ldots, a_n $ 和 $ b_1, b_2, \ldots, b_n $。需要处理 $ q $ 次以下两种类型的查询： - $ 1 $ $ l $ $ r $ $ x $ : 将 $ a_i $ 的值赋为 $ x $ 对于所有 $ l \leq i \leq r $； - $ 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 $ 行以整数 $ 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 $ 的查询。 **输出格式** 对于每个类型为 $ 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