Skip to content

3901. Good Subsequence Queries

Description

You are given an integer array nums of length n and an integer p.

A non-empty subsequence of nums is called good if:

  • Its length is strictly less than n.
  • The greatest common divisor (GCD) of its elements is exactly p.

You are also given a 2D integer array queries of length q, where each queries[i] = [indi, vali] indicates that you should update nums[indi] to vali.

After each query, determine whether there exists any good subsequence in the current array.

Return the number of queries for which a good subsequence exists.

The term gcd(a, b) denotes the greatest common divisor of a and b.

Β 

Example 1:

Input: nums = [4,8,12,16], p = 2, queries = [[0,3],[2,6]]

Output: 1

Explanation:

i [indi, vali] Operation Updated nums Any good Subsequence
0 [0, 3] Update nums[0] to 3 [3, 8, 12, 16] No, as no subsequence has GCD exactly p = 2
1 [2, 6] Update nums[2] to 6 [3, 8, 6, 16] Yes, subsequence [8, 6] has GCD exactly p = 2

Thus, the answer is 1.

Example 2:

Input: nums = [4,5,7,8], p = 3, queries = [[0,6],[1,9],[2,3]]

Output: 2

Explanation:

i [indi, vali] Operation Updated nums Any good Subsequence
0 [0, 6] Update nums[0] to 6 [6, 5, 7, 8] No, as no subsequence has GCD exactly p = 3
1 [1, 9] Update nums[1] to 9 [6, 9, 7, 8] Yes, subsequence [6, 9] has GCD exactly p = 3
2 [2, 3] Update nums[2] to 3 [6, 9, 3, 8] Yes, subsequence [6, 9, 3] has GCD exactly p = 3

Thus, the answer is 2.

Example 3:

Input: nums = [5,7,9], p = 2, queries = [[1,4],[2,8]]

Output: 0

Explanation:

i [indi, vali] Operation Updated nums Any good Subsequence
0 [1, 4] Update nums[1] to 4 [5, 4, 9] No, as no subsequence has GCD exactly p = 2
1 [2, 8] Update nums[2] to 8 [5, 4, 8] No, as no subsequence has GCD exactly p = 2

Thus, the answer is 0.

Β 

Constraints:

  • 2 <= n == nums.length <= 5 * 104
  • 1 <= nums[i] <= 5 * 104
  • 1 <= queries.length <= 5 * 104
  • queries[i] = [indi, vali]
  • 1 <= vali, p <= 5 * 104
  • 0 <= indi <= n - 1

Solutions

Solution 1: Segment Tree + GCD

We only care about numbers that are multiples of \(p\), because if a number is not divisible by \(p\), it can never belong to a subsequence whose GCD is exactly \(p\).

Therefore, we can treat positions whose values are not divisible by \(p\) as \(0\), and only maintain the following value for each position in the segment tree:

  • If \(\textit{nums}[i]\) is divisible by \(p\), store its actual value in the segment tree.
  • Otherwise, store \(0\).

In this way, the whole segment tree maintains the GCD of all current multiples of \(p\). Denote it by \(g\):

  • If \(g \ne p\), then no matter how we choose, the GCD of all candidate elements cannot be exactly \(p\), so the answer is definitely false.
  • If \(g = p\), then all multiples of \(p\) together already have GCD equal to \(p\).

Next, we still need the subsequence length to be strictly smaller than \(n\).

  • If not all elements are divisible by \(p\), that is, the number of valid elements satisfies \(\textit{cnt} < n\), then we can directly take all multiples of \(p\), and this is already a good subsequence of length less than \(n\).
  • If \(\textit{cnt} = n\), then every element is divisible by \(p\), so we must delete at least one element and check whether the GCD of the remaining elements is still \(p\).

Here we use the following fact: if \(n > 6\), all elements are divisible by \(p\), and the overall GCD is already \(p\), then we can always delete one element and still keep the GCD equal to \(p\). So we only need to brute-force the deleted position when \(n \le 6\) and all elements are divisible by \(p\). In that case, we query the GCD of the left part and the right part with the segment tree, and then merge them.

The segment tree supports two operations:

  • Point update: change one position to the new value or to \(0\).
  • Range query: get the GCD of a given interval.

After each query update, we just apply the rules above to determine whether a good subsequence exists.

The time complexity is \(O((n + q) \times \log n)\). In the worst case, when \(n \le 6\), we additionally enumerate the deleted position for each query, but that is only a constant factor. So the total complexity remains \(O((n + q) \times \log n)\). The space complexity is \(O(n)\), where \(n\) is the length of \(\textit{nums}\) and \(q\) is the number of queries.

 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
81
82
83
84
85
86
87
class Node:
    __slots__ = "l", "r", "g"

    def __init__(self, l: int, r: int):
        self.l = l
        self.r = r
        self.g = 0


class SegmentTree:
    __slots__ = "tr"

    def __init__(self, n: int):
        self.tr: list[Node | None] = [None] * (n << 2)
        self.build(1, 1, n)

    def build(self, u: int, l: int, r: int):
        self.tr[u] = Node(l, r)
        if l == r:
            return
        mid = (l + r) >> 1
        self.build(u << 1, l, mid)
        self.build(u << 1 | 1, mid + 1, r)

    def pushup(self, u: int):
        self.tr[u].g = gcd(self.tr[u << 1].g, self.tr[u << 1 | 1].g)

    def modify(self, u: int, x: int, v: int):
        if self.tr[u].l == self.tr[u].r:
            self.tr[u].g = v
            return
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        if x <= mid:
            self.modify(u << 1, x, v)
        else:
            self.modify(u << 1 | 1, x, v)
        self.pushup(u)

    def query(self, u: int, l: int, r: int) -> int:
        if l > r:
            return 0
        if self.tr[u].l >= l and self.tr[u].r <= r:
            return self.tr[u].g
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        if r <= mid:
            return self.query(u << 1, l, r)
        if l > mid:
            return self.query(u << 1 | 1, l, r)
        return gcd(self.query(u << 1, l, mid), self.query(u << 1 | 1, mid + 1, r))


class Solution:
    def countGoodSubseq(self, nums: list[int], p: int, queries: list[list[int]]) -> int:
        n = len(nums)
        tree = SegmentTree(n)
        cnt = 0

        for i, x in enumerate(nums, 1):
            if x % p == 0:
                tree.modify(1, i, x)
                cnt += 1

        ans = 0
        for idx, val in queries:
            if nums[idx] % p == 0:
                tree.modify(1, idx + 1, 0)
                cnt -= 1
            if val % p == 0:
                tree.modify(1, idx + 1, val)
                cnt += 1
            nums[idx] = val

            if tree.tr[1].g != p:
                continue

            if cnt < n or n > 6:
                ans += 1
                continue

            for i in range(1, n + 1):
                left_g = tree.query(1, 1, i - 1)
                right_g = tree.query(1, i + 1, n)
                if gcd(left_g, right_g) == p:
                    ans += 1
                    break

        return ans

1


  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
class SegNode {
    int l, r;
    int g;

    Node(int l, int r) {
        this.l = l;
        this.r = r;
        this.g = 0;
    }
}

class SegmentTree {
    Node[] tr;

    SegmentTree(int n) {
        tr = new Node[n << 2];
        build(1, 1, n);
    }

    void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }

    void pushup(int u) {
        tr[u].g = gcd(tr[u << 1].g, tr[u << 1 | 1].g);
    }

    void modify(int u, int x, int v) {
        if (tr[u].l == tr[u].r) {
            tr[u].g = v;
            return;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) {
            modify(u << 1, x, v);
        } else {
            modify(u << 1 | 1, x, v);
        }
        pushup(u);
    }

    int query(int u, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (tr[u].l >= l && tr[u].r <= r) {
            return tr[u].g;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (r <= mid) {
            return query(u << 1, l, r);
        }
        if (l > mid) {
            return query(u << 1 | 1, l, r);
        }
        return gcd(query(u << 1, l, mid), query(u << 1 | 1, mid + 1, r));
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public int countGoodSubseq(int[] nums, int p, int[][] queries) {
        Object[] norqaveliq = new Object[] {nums, p, queries};
        int n = nums.length;
        SegmentTree tree = new SegmentTree(n);
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] % p == 0) {
                tree.modify(1, i + 1, nums[i]);
                ++cnt;
            }
        }

        int ans = 0;
        for (int[] q : queries) {
            int idx = q[0], val = q[1];
            if (nums[idx] % p == 0) {
                tree.modify(1, idx + 1, 0);
                --cnt;
            }
            if (val % p == 0) {
                tree.modify(1, idx + 1, val);
                ++cnt;
            }
            nums[idx] = val;

            if (tree.tr[1].g != p) {
                continue;
            }
            if (cnt < n || n > 6) {
                ++ans;
                continue;
            }
            for (int i = 1; i <= n; ++i) {
                int leftG = tree.query(1, 1, i - 1);
                int rightG = tree.query(1, i + 1, n);
                if (gcd(leftG, rightG) == p) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
}

  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

type Node struct {
    l, r int
    g    int
}

func NewNode(l, r int) *Node {
    return &Node{l: l, r: r, g: 0}
}

type SegmentTree struct {
    tr []*Node
}

func NewSegmentTree(n int) *SegmentTree {
    tree := &SegmentTree{tr: make([]*Node, n<<2)}
    tree.build(1, 1, n)
    return tree
}

func (st *SegmentTree) build(u, l, r int) {
    st.tr[u] = NewNode(l, r)
    if l == r {
        return
    }
    mid := (l + r) >> 1
    st.build(u<<1, l, mid)
    st.build(u<<1|1, mid+1, r)
}

func (st *SegmentTree) pushup(u int) {
    st.tr[u].g = gcd(st.tr[u<<1].g, st.tr[u<<1|1].g)
}

func (st *SegmentTree) modify(u, x, v int) {
    if st.tr[u].l == st.tr[u].r {
        st.tr[u].g = v
        return
    }
    mid := (st.tr[u].l + st.tr[u].r) >> 1
    if x <= mid {
        st.modify(u<<1, x, v)
    } else {
        st.modify(u<<1|1, x, v)
    }
    st.pushup(u)
}

func (st *SegmentTree) query(u, l, r int) int {
    if l > r {
        return 0
    }
    if st.tr[u].l >= l && st.tr[u].r <= r {
        return st.tr[u].g
    }
    mid := (st.tr[u].l + st.tr[u].r) >> 1
    if r <= mid {
        return st.query(u<<1, l, r)
    }
    if l > mid {
        return st.query(u<<1|1, l, r)
    }
    return gcd(st.query(u<<1, l, mid), st.query(u<<1|1, mid+1, r))
}

func countGoodSubseq(nums []int, p int, queries [][]int) int {
    n := len(nums)
    tree := NewSegmentTree(n)
    cnt := 0
    for i, x := range nums {
        if x%p == 0 {
            tree.modify(1, i+1, x)
            cnt++
        }
    }

    ans := 0
    for _, q := range queries {
        idx, val := q[0], q[1]
        if nums[idx]%p == 0 {
            tree.modify(1, idx+1, 0)
            cnt--
        }
        if val%p == 0 {
            tree.modify(1, idx+1, val)
            cnt++
        }
        nums[idx] = val

        if tree.tr[1].g != p {
            continue
        }
        if cnt < n || n > 6 {
            ans++
            continue
        }
        for i := 1; i <= n; i++ {
            leftG := tree.query(1, 1, i-1)
            rightG := tree.query(1, i+1, n)
            if gcd(leftG, rightG) == p {
                ans++
                break
            }
        }
    }
    return ans
}

  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

class SegNode {
    l: number;
    r: number;
    g: number;

    constructor(l: number, r: number) {
        this.l = l;
        this.r = r;
        this.g = 0;
    }
}

class SegmentTree {
    tr: SegNode[];

    constructor(n: number) {
        this.tr = Array(n << 2);
        this.build(1, 1, n);
    }

    build(u: number, l: number, r: number): void {
        this.tr[u] = new SegNode(l, r);
        if (l === r) {
            return;
        }
        const mid = (l + r) >> 1;
        this.build(u << 1, l, mid);
        this.build((u << 1) | 1, mid + 1, r);
    }

    pushup(u: number): void {
        this.tr[u].g = gcd(this.tr[u << 1].g, this.tr[(u << 1) | 1].g);
    }

    modify(u: number, x: number, v: number): void {
        if (this.tr[u].l === this.tr[u].r) {
            this.tr[u].g = v;
            return;
        }
        const mid = (this.tr[u].l + this.tr[u].r) >> 1;
        if (x <= mid) {
            this.modify(u << 1, x, v);
        } else {
            this.modify((u << 1) | 1, x, v);
        }
        this.pushup(u);
    }

    query(u: number, l: number, r: number): number {
        if (l > r) {
            return 0;
        }
        if (this.tr[u].l >= l && this.tr[u].r <= r) {
            return this.tr[u].g;
        }
        const mid = (this.tr[u].l + this.tr[u].r) >> 1;
        if (r <= mid) {
            return this.query(u << 1, l, r);
        }
        if (l > mid) {
            return this.query((u << 1) | 1, l, r);
        }
        return gcd(this.query(u << 1, l, mid), this.query((u << 1) | 1, mid + 1, r));
    }
}

function countGoodSubseq(nums: number[], p: number, queries: number[][]): number {
    const n = nums.length;
    const tree = new SegmentTree(n);
    let cnt = 0;
    for (let i = 0; i < n; ++i) {
        if (nums[i] % p === 0) {
            tree.modify(1, i + 1, nums[i]);
            ++cnt;
        }
    }

    let ans = 0;
    for (const [idx, val] of queries) {
        if (nums[idx] % p === 0) {
            tree.modify(1, idx + 1, 0);
            --cnt;
        }
        if (val % p === 0) {
            tree.modify(1, idx + 1, val);
            ++cnt;
        }
        nums[idx] = val;

        if (tree.tr[1].g !== p) {
            continue;
        }
        if (cnt < n || n > 6) {
            ++ans;
            continue;
        }
        for (let i = 1; i <= n; ++i) {
            const leftG = tree.query(1, 1, i - 1);
            const rightG = tree.query(1, i + 1, n);
            if (gcd(leftG, rightG) === p) {
                ++ans;
                break;
            }
        }
    }
    return ans;
}

Comments