题目链接：传送门

Description

Bash likes playing with arrays. He has an array a1, a2, ... an of n integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is almost correct. Suppose he guesses that the gcd of the elements in the range [l, r] of a is x. He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is x after making the change. Note that when he guesses, he doesn't actually change the array — he just wonders if the gcd of the segment can be made x. Apart from this, he also sometimes makes changes to the array itself. Since he can't figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process q queries of one of the following forms:

  • 1 l r x — Bash guesses that the gcd of the range [l, r] is x. Report if this guess is almost correct.
  • 2 i y — Bash sets ai to y. Note: The array is 1-indexed.

Input

The first line contains an integer n (1 ≤ n ≤ 5·10^5) — the size of the array. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^9) — the elements of the array. The third line contains an integer q (1 ≤ q ≤ 4·10^5) — the number of queries. The next q lines describe the queries and may have one of the following forms:

  • 1 l r x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^9).
  • 2 i y (1 ≤ i ≤ n, 1 ≤ y ≤ 10^9). Guaranteed, that there is at least one query of first type.

Output

For each query of first type, output "YES" (without quotes) if Bash's guess is almost correct and "NO" (without quotes) otherwise.

Sample Input

3 2 6 3 4 1 1 2 2 1 1 3 3 2 1 9 1 1 3 2

Sample Output

YES YES NO

Solution

题意：n个数的数列，对它有下面两种操作

  • 猜 l ~ r 这部分数的最大公因数为x，如果x不是最大公因数，但只改变l ~ r中的一个数就能让x是最大公因数，那么可以认为是猜中了
  • 把某一个数 i 的值变为 y 用线段树维护一下Gcd， 更新直接单点修改，查询的时候求出区间内不是x的倍数的数量，如果大于1则输出No，否则输出YES

只是查询时要加一个剪枝，如果ans大于1则不需要向下递归，直接return

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 500000 + 100;
int Tree[Maxn * 4];
int N, M;

inline int Gcd (int a, int b)
{
    return b ? Gcd(b, a % b) : a;
}

inline void Push_up(int root)
{
    Tree[root] = Gcd(Tree[root << 1], Tree[root << 1 | 1]);
}

inline void build (int root, int l, int r)
{
    if (l == r)
    {
        scanf("%d", &Tree[root]);
        return ;
    }
    int mid = (l + r) >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    Push_up(root);
}

inline void Update(int root, int l, int r, int x, int y)
{
    if (l == r)
    {
        Tree[root] = y;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) Update(root << 1, l, mid, x, y);
    else Update(root << 1 | 1, mid + 1, r, x, y);
    Push_up(root);
}

inline int Query(int root, int l, int r, int x, int y, int z)
{
    if (l == r) return 1;
    int mid = (l + r) >> 1, Ans = 0;
    if (x <= mid && Tree[root << 1] % z)
        Ans += Query(root << 1, l, mid, x, y, z);
    if (y > mid && Tree[root << 1 | 1] % z && Ans <= 1)
        Ans += Query(root << 1 | 1, mid + 1, r, x, y, z);
    return Ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
#endif
    scanf("%d", &N);
    build(1, 1, N);
    scanf("%d", &M);
    for (int i = 1; i <= M; ++i)
    {
        int type, x, y, z;
        scanf("%d", &type);
        if (type == 1)
        {
            scanf("%d%d%d", &x, &y, &z);
            if (Query(1, 1, N, x, y, z) <= 1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        else 
        {
            scanf("%d%d", &x, &y);
            Update(1, 1, N, x, y);
        }
    }
    return 0;
}