**Definitions:**
- Let $ a = [a_1, a_2, \dots, a_n] $ be an array of $ n $ positive integers, 1-indexed.
- Let $ \gcd(S) $ denote the greatest common divisor of a multiset $ S $ of integers.
- A query is of one of two types:
1. **Guess Query**: Given $ l, r, x $, determine whether there exists an index $ i \in [l, r] $ such that replacing $ a_i $ with some integer $ b $ yields $ \gcd(a_l, \dots, a_{i-1}, b, a_{i+1}, \dots, a_r) = x $, **or** $ \gcd(a_l, \dots, a_r) = x $ (i.e., no change needed).
2. **Update Query**: Given $ i, v $, set $ a_i \leftarrow v $.
**Constraints:**
- $ 1 \leq n \leq 5 \cdot 10^5 $
- $ 1 \leq a_i \leq 10^9 $
- $ 1 \leq q \leq 4 \cdot 10^5 $
- Queries of type 1 are guaranteed to exist.
**Objective:**
For each query of type 1 with parameters $ (l, r, x) $, output:
- **"YES"** if **at most one** element in $ a[l:r] $ can be replaced (with any positive integer) so that the gcd of the resulting segment equals $ x $,
- **"NO"** otherwise.
**Formal Condition for "YES":**
Let $ G = \gcd(a_l, a_{l+1}, \dots, a_r) $.
Define $ g_i = \gcd(\{a_j : j \in [l, r], j \ne i\}) $ for each $ i \in [l, r] $.
Then, the guess is almost correct **iff**:
$$
\exists\, i \in [l, r] \text{ such that } g_i \text{ is divisible by } x \quad \text{and} \quad \frac{g_i}{x} \text{ is an integer} \quad \text{and} \quad \exists\, b \in \mathbb{Z}^+ \text{ such that } \gcd(g_i, b) = x
$$
But since we can choose $ b $ arbitrarily, the condition simplifies to:
> There exists an index $ i \in [l, r] $ such that $ x \mid g_i $,
> **or** $ G = x $ (i.e., no change needed).
Equivalently, since $ \gcd(g_i, b) = x $ is achievable for some $ b $ if and only if $ x \mid g_i $, the condition becomes:
$$
\boxed{
\exists\, i \in [l, r] \text{ such that } x \mid \gcd(\{a_j : j \in [l, r], j \ne i\})
}
$$
**Note:** If $ x \mid G $, then setting $ b = x $ (or any multiple of $ x $) may not work unless the other elements’ gcd is divisible by $ x $. But the above condition captures it: if $ x \mid g_i $, then we can choose $ b = x $, and the overall gcd becomes $ \gcd(g_i, x) = x $, since $ x \mid g_i $.
Thus, the necessary and sufficient condition is:
> The guess $ x $ is almost correct for segment $ [l, r] $ **iff**
> $$
> \exists\, i \in [l, r] \text{ such that } x \mid \gcd_{j \in [l, r] \setminus \{i\}} a_j
> $$
This includes the case $ i $ is not changed (i.e., $ \gcd_{j \in [l, r]} a_j = x $), because then $ g_i = \gcd_{j \ne i} a_j $ still satisfies $ x \mid g_i $ (since $ x = G \mid g_i $ only if $ g_i = G $, which is true only if removing $ a_i $ doesn't change the gcd — but actually, if $ G = x $, then for *any* $ i $, we have $ x \mid g_i $? Not necessarily. So we must be careful.
Actually, if $ G = x $, then we don't need to change anything. So we can always choose to change *no* element. So we must allow the case of **zero changes**.
Therefore, the condition is:
$$
\boxed{
\gcd(a_l, \dots, a_r) = x \quad \text{OR} \quad \exists\, i \in [l, r] \text{ such that } x \mid \gcd(\{a_j : j \in [l, r], j \ne i\})
}
$$
But note: if $ \gcd(a_l, \dots, a_r) = x $, then for *every* $ i $, $ g_i $ is a multiple of $ x $? Not necessarily. For example: $ [6, 10] $, $ x = 2 $. $ \gcd(6,10)=2 $, but $ g_1 = 10 $, $ g_2 = 6 $, both divisible by 2 — so yes. But is it always true?
Suppose $ G = x $. Then $ x \mid a_j $ for all $ j $. So for any $ i $, $ g_i = \gcd(\text{all except } a_i) $, which is still divisible by $ x $, since all other $ a_j $ are divisible by $ x $. So yes: if $ G = x $, then for **every** $ i $, $ x \mid g_i $.
Thus, the condition "there exists $ i \in [l, r] $ such that $ x \mid g_i $" **includes** the case $ G = x $.
Therefore, the entire condition reduces to:
$$
\boxed{
\exists\, i \in [l, r] \text{ such that } x \mid \gcd\left( \{a_j : j \in [l, r],\ j \ne i\} \right)
}
$$
This is the formal condition to check for each query of type 1.
**Update queries** modify $ a_i \leftarrow v $, and are handled directly.
**Implementation note:** To compute $ g_i = \gcd(\text{prefix}[i-1], \text{suffix}[i+1]) $ efficiently for all $ i \in [l, r] $, we can precompute prefix and suffix gcd arrays for any range, but since queries are online and updates occur, we need a segment tree or similar data structure supporting:
- Point updates
- Range gcd queries
- For a given range $ [l, r] $ and value $ x $, check: $ \exists i \in [l, r] $ such that $ x \mid \gcd(\text{all elements in } [l, r] \setminus \{i\}) $
The latter can be done by computing the total gcd $ G = \gcd(a_l, \dots, a_r) $, and for each $ i $, $ g_i = \gcd(\gcd(a_l, \dots, a_{i-1}), \gcd(a_{i+1}, \dots, a_r)) $.
We can precompute prefix and suffix gcd arrays for any segment $ [l, r] $ in $ O(1) $ after $ O(n) $ preprocessing per segment — but since segments vary per query and updates occur, we need a segment tree that supports:
- Point updates
- Range gcd queries
- And for a given $ [l, r] $, compute $ g_i $ for each $ i \in [l, r] $ in $ O(1) $ per index — which would be $ O(r-l+1) $, too slow.
Alternative insight:
Let $ G = \gcd(a_l, \dots, a_r) $
We want to know: is there an index $ i \in [l, r] $ such that $ x \mid \gcd_{j \ne i} a_j $?
Let $ g_i = \gcd(\text{all except } a_i) $
Note: $ \gcd(g_i, a_i) = G $
So $ g_i = \frac{G}{\gcd(G, a_i)} \cdot \text{something} $? Not exactly.
Actually, $ G = \gcd(g_i, a_i) $
So $ g_i = \frac{G}{d_i} $ where $ d_i = \gcd(G, a_i) $? Not quite.
Better: $ G \mid g_i $, because $ G $ divides every $ a_j $, so $ G \mid g_i $. So $ g_i $ is a multiple of $ G $.
Wait: no! $ g_i $ is the gcd of all elements except $ a_i $, and $ G $ is the gcd of all elements. So $ G \mid g_i $, because $ g_i $ is a common divisor of a subset of the elements, and $ G $ divides all elements, so $ G \mid g_i $.
Therefore, $ g_i $ is a multiple of $ G $. So $ x \mid g_i $ implies $ x \mid g_i $ and $ G \mid g_i $.
But we are not requiring $ x \mid G $. We are requiring $ x \mid g_i $.
So: we want to know if there exists $ i \in [l, r] $ such that $ x \mid g_i $, where $ g_i = \gcd_{j \ne i} a_j $.
And since $ g_i = \gcd( \gcd(a_l, \dots, a_{i-1}), \gcd(a_{i+1}, \dots, a_r) ) $, we can compute $ g_i $ for each $ i $ using prefix and suffix arrays for the range $ [l, r] $.
So for a fixed query $ [l, r] $, we can:
1. Precompute prefix gcd: $ P[i] = \gcd(a_l, a_{l+1}, \dots, a_i) $ for $ i = l $ to $ r $
2. Precompute suffix gcd: $ S[i] = \gcd(a_i, a_{i+1}, \dots, a_r) $ for $ i = l $ to $ r $
3. For each $ i \in [l, r] $, compute $ g_i = \gcd(P[i-1], S[i+1]) $ (with appropriate bounds)
4. Check if $ x \mid g_i $ for any $ i $
But doing this for each query would be $ O(n) $ per query, and $ q \leq 4 \cdot 10^5 $, so worst-case $ O(nq) \approx 2 \cdot 10^{11} $, too slow.
We need a better approach.
**Key Insight:**
Let $ G = \gcd(a_l, \dots, a_r) $
We want to know: does there exist an index $ i $ such that $ x \mid \gcd_{j \ne i} a_j $?
Note that $ \gcd_{j \ne i} a_j = \frac{G}{\gcd(G, a_i)} \cdot k $? Not exactly.
Actually, we have:
$$
\gcd_{j \ne i} a_j = \frac{G}{\gcd(G, a_i / \gcd(G, a_i))} \quad \text{? No.}
$$
Better: Since $ G = \gcd(g_i, a_i) $, and $ g_i $ is divisible by $ G $, then $ g_i = G \cdot d_i $ for some integer $ d_i \geq 1 $.
But $ d_i = \frac{g_i}{G} $, and $ \gcd(a_i / G, d_i) = 1 $.
We want $ x \mid g_i = G \cdot d_i $
So $ x \mid G \cdot d_i $
Let $ d = \gcd(x, G) $. Then $ x = d \cdot x' $, $ G = d \cdot G' $, and $ \gcd(x', G') = 1 $
Then $ x \mid G \cdot d_i \iff d \cdot x' \mid d \cdot G' \cdot d_i \iff x' \mid G' \cdot d_i $
Since $ \gcd(x', G') = 1 $, this implies $ x' \mid d_i $
So $ d_i \geq x' $
But $ d_i = g_i / G $, and $ g_i $ is the gcd of all except $ a_i $, so $ d_i $ is the "extra" factor from removing $ a_i $.
This is getting complex.
**Practical known solution from similar problems (e.g., Codeforces):**
The standard solution for "almost gcd" queries is:
- For a query $ (l, r, x) $, compute $ G = \gcd(a_l, \dots, a_r) $
- If $ x \mid G $, then YES (because we can change any element to $ x $, and since all others are divisible by $ x $, the gcd becomes $ x $) — **Wait, no!** If $ x \mid G $, then $ G $ is a multiple of $ x $, so $ x $ divides all elements? No: $ G $ divides all elements, so if $ x \mid G $, then $ x $ divides all elements. So we can change any element to $ x $, and the gcd becomes $ \gcd(x, \text{other elements}) $. But since other elements are divisible by $ G $, which is divisible by $ x $, then $ \gcd(x, \text{multiple of } x) = x $. So YES.
But what if $ x \nmid G $? Then we need to change exactly one element.
Let’s suppose $ x \nmid G $. Then we must change one element $ a_i $ such that $ \gcd(\text{others}) $ is divisible by $ x $, and then we set $ a_i $ to $ x $, so the overall gcd becomes $ \gcd(\gcd(\text{others}), x) = x $, since $ x \mid \gcd(\text{others}) $.
So condition: $ \exists i \in [l, r] $ such that $ x \mid \gcd_{j \ne i} a_j $
And since $ \gcd_{j \ne i} a_j = \frac{G}{\gcd(G, a_i)} \cdot \text{?} $
Actually, a known trick:
Let $ G = \gcd(a_l, \dots, a_r) $
For each $ i $, define $ g_i = \gcd(\text{all except } a_i) $
Then $ g_i = \gcd(G, \text{all except } a_i) = \gcd(G, \text{gcd of all except } a_i) $ — tautology.
But note: $ g_i = \frac{G}{\gcd(G, a_i / \gcd(G, a_i))} $? No.
Actually, since $ G = \gcd(g_i, a_i) $, then $ g_i = \frac{G \cdot k}{\gcd(k, a_i / \gcd(G, a_i))} $ — messy.
Standard solution from Codeforces problems (e.g., CF 1114D, CF 1175E) for "can we change one element to make gcd = x":
1. Compute $ G = \gcd(a_l, \dots, a_r) $
2. If $ x \mid G $: YES
3. Else:
- For each $ i \in [l, r] $, compute $ g_i = \gcd(\text{prefix}[i-1], \text{suffix}[i+1]) $
- Check if $ x \mid g_i $ for any $ i $
- If yes, YES; else NO
But we can’t iterate over all $ i $ per query.
**Optimization:**
We can note: if there exists an index $ i $ such that $ x \mid g_i $, then since $ g_i $ is the gcd of all elements except $ a_i $, and $ G = \gcd(g_i, a_i) $, then $ g_i $ must be divisible by $ x $, and $ G $ is a divisor of $ g_i $.
So $ \text{lcm}(G, x) \mid g_i $? Not helpful.
Another idea: the number of indices $ i $ for which $ g_i \ne G $ is small. In fact, $ g_i \ne G $ only if $ a_i $ is the unique element that is not divisible by some prime factor of $ G $. So there are at most $ O(\log \max a_i) $ such indices.
Thus, we can find all indices $ i \in [l, r] $ such that $ \gcd(a_l, \dots, a_r) \ne \gcd(a_l, \dots, a_{i-1}, a_{i+1}, \dots, a_r) $ — i.e., the indices where removing $ a_i $ changes the gcd. There are at most $ O(\log \max a_i) $ such indices, because each time the gcd changes, it drops by a factor of at least 2.
So algorithm for a query $ (l, r, x) $:
1. Compute $ G = \gcd(a_l, \dots, a_r) $
2. If $ x \mid G $: return YES
3. Else:
- Find all indices $ i \in [l, r] $ such that $ g_i \ne G $. These are the "critical" indices where removing $ a_i $ increases the gcd (or changes it). There are at most $ O(\log \max a_i) $ such indices.
- For each such $ i $, compute $ g_i = \gcd(\text{prefix}[i-1], \text{suffix}[i+1]) $
- If $ x \mid g_i $ for any such $ i $, return YES
- Else, return NO
How to find critical indices quickly?
We can use a segment tree that stores gcd, and then do a binary search-like traversal to find all positions where the gcd changes when skipping an element.
Alternatively, we can precompute for the entire array a structure that allows us to, for a given range $ [l, r] $, iterate over the "distinct gcd prefixes" — but this is complex.
Known efficient solution: use a segment tree storing gcd, and for a query $ [l, r] $, we can compute the prefix and suffix gcd arrays in $ O(\log n) $ time per query if we store them in a segment tree — but we need all $ g_i $.
Actually, we can do:
- Use a segment tree to get $ \gcd(l, r) $
- Use a segment tree to get prefix gcd from $ l $ to any $ i $, and suffix gcd from any $ i $ to $ r $
- Then, for the entire range $ [l, r] $, we can find the positions where the prefix gcd changes — there are at most $ O(\log \max a_i) $ such changes.
So we can:
- Compute prefix gcd array for $ [l, r] $ by walking through the segment tree and collecting the distinct gcd values and their positions — at most $ O(\log n) $ distinct values.
- Similarly for suffix.
- Then, for each position where the prefix gcd changes, and for each where the suffix gcd changes, we can compute $ g_i $ for those candidate indices.
In fact, the only indices $ i $ that can yield $ g_i \ne G $ are those where $ a_i $ is the "odd one out" — and there are at most $ O(\log \max a_i) $ such candidates.
So practical solution:
For query $ (l, r, x) $:
1. Compute $ G = \gcd(a_l, \dots, a_r) $
2. If $ x \mid G $: return YES
3. Else:
- Let $ \text{candidates} = \emptyset $
- Compute the prefix gcd array from $ l $ to $ r $, and record the indices where it changes: $ i_1, i_2, \dots, i_k $ (at most $ O(\log \max a_i) $)
- Similarly compute suffix gcd array from $ r $ to $ l $, record change points: $ j_1, j_2, \dots, j_m $
- The candidate indices for $ i $ are the union of these change points and $ l, r $ — total $ O(\log \max a_i) $
- For each candidate $ i \in \text{candidates} \cap [l, r] $:
- Compute $ g_i = \gcd(\text{prefix}[i-1], \text{suffix}[i+1]) $
- If $ x \mid g_i $, return YES
- Return NO
This works because if $ g_i \ne G $, then $ a_i $ must be the reason for the gcd being $ G $, and removing it must cause a change — and there are only logarithmically many such elements.
**Final Formal Statement:**
Given array $ a $, and queries:
- **Update**: $ a_i \leftarrow v $
- **Query**: Given $ l, r, x $, output YES iff
$$
x \mid \gcd(a_l, \dots, a_r) \quad \text{or} \quad \exists\, i \in [l, r] \text{ such that } x \mid \gcd(\{a_j : j \in [l, r], j \ne i\})
$$
And due to the structure of gcd, the second condition can be checked by examining only $ O(\log \max a_i) $ candidate indices per query.
Thus, the formal condition is as above.