CF914D Bash and a Tough Math Puzzle

Bash 喜欢玩数组。他有一个由 $n$ 个整数构成的数组 $a_1, a_2, \ldots, a_n$。他喜欢猜测数组不同区间的最大公约数（gcd）。当然，有时候他的猜测并不正确。不过，如果他的猜测“几乎正确”，他也会感到满足。 假设他猜测区间 $[l,r]$ 内所有元素的 gcd 为 $x$。如果他能通过至多修改该区间内的一个元素，使得区间的 gcd 等于 $x$，那么他的猜测就被认为是“几乎正确”的。注意，他在猜测的时候并不会真的修改数组——他只是想知道通过修改一个元素，区间的 gcd 是否能够变为 $x$。除此以外，他有时也会真的修改数组中的元素。 因为他自己搞不清楚，所以 Bash 想让你帮他判断他的哪些猜测是“几乎正确”的。形式上，你需要处理 $q$ 个如下两种形式的操作： - $1\ l\ r\ x$ — Bash 猜测区间 $[l, r]$ 的 gcd 为 $x$，请回答他的猜测是否“几乎正确”。 - $2\ i\ y$ — 将 $a_i$ 修改为 $y$。 注意：数组是从 $1$ 开始编号的。

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）——数组的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）——数组的元素。 第三行包含一个整数 $q$（$1 \leq q \leq 4 \cdot 10^5$）——操作的数量。 接下来的 $q$ 行描述各次操作，每行有以下两种形式之一： - $1\ l\ r\ x$（$1 \leq l \leq r \leq n,\, 1 \leq x \leq 10^9$）。 - $2\ i\ y$（$1 \leq i \leq n,\, 1 \leq y \leq 10^9$）。 保证至少有一个第一种类型的操作。

对于每个第一种类型的操作，如果 Bash 的猜测“几乎正确”，输出 "YES"（不含引号）；否则输出 "NO"（不含引号）。

在第一个样例中，初始数组为 ${2,6,3}$。 对于第 $1$ 个操作，前两个数的 gcd 已经是 $2$。 对于第 $2$ 个操作，我们可以通过将数组的第一个元素改为 $3$，使得区间的 gcd 为 $3$。注意类型 $1$ 的操作中的更改是临时的，不会影响实际数组。 第 $3$ 个操作后，数组变为 ${9,6,3}$。 第 $4$ 个操作中，无论怎么修改区间内的哪个元素，都无法使区间的 gcd 变为 $2$。 由 ChatGPT 5 翻译