CF1732E Location

给定两个整数数组 $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$ 的 $i$ 中，求如下表达式的最小值：$$\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 = 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$ 的操作，输出该表达式的最小值。

在第一个样例中： - 对于第一个操作，可以选择 $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$。 由 ChatGPT 4.1 翻译