Welcome to Subscribe On Youtube
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 * 1041 <= nums[i] <= 5 * 1041 <= queries.length <= 5 * 104queries[i] = [indi, vali]1 <= vali, p <= 5 * 1040 <= 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.
-
class Node { 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) { 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; } } -
class Node { public: int l, r; int g; Node(int l, int r) : l(l) , r(r) , g(0) {} }; class SegmentTree { public: vector<Node*> tr; SegmentTree(int n) : tr(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)); } ~SegmentTree() { for (auto node : tr) { delete node; } } }; class Solution { public: int countGoodSubseq(vector<int>& nums, int p, vector<vector<int>>& queries) { int n = nums.size(); SegmentTree tree(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 (auto& 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; } }; -
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 -
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 } -
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; }