根据搜索结果LeetCode 3901「好子序列查询」的 Python3 实现如下---思路1. 只关心 p 的倍数如果 nums[i] 不是 p 的倍数它对 GCD 为 p 的子序列没有贡献在线段树中视为 0。2. 线段树维护所有 p 倍数的 GCD记为 g。- 若 g ! p则不存在好子序列。- 若 g p则所有 p 的倍数整体 GCD 已是 p。3. 长度严格小于 n- 若 cnt n并非所有元素都是 p 的倍数直接取所有 p 的倍数即可长度必然 n。- 若 cnt n所有元素都是 p 的倍数需要删一个元素后 GCD 仍为 p。- 关键结论若 n 6 且整体 GCD 为 p则一定可以删一个元素使 GCD 仍为 p。因此只需在 n 6 时暴力枚举删除位置。4. 线段树操作单点更新、区间查询 GCD。---Python3 实现pythonfrom math import gcdclass Node:__slots__ l, r, gdef __init__(self, l: int, r: int):self.l lself.r rself.g 0class SegmentTree:__slots__ trdef __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:returnmid (l r) 1self.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 vreturnmid (self.tr[u].l self.tr[u].r) 1if 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 0if self.tr[u].l l and self.tr[u].r r:return self.tr[u].gmid (self.tr[u].l self.tr[u].r) 1if 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 0for i, x in enumerate(nums, 1):if x % p 0:tree.modify(1, i, x)cnt 1ans 0for idx, val in queries:if nums[idx] % p 0:tree.modify(1, idx 1, 0)cnt - 1if val % p 0:tree.modify(1, idx 1, val)cnt 1nums[idx] valif tree.tr[1].g ! p:continueif cnt n or n 6:ans 1continuefor 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 1breakreturn ans---复杂度- 时间复杂度O((n q) \times \log n)其中 n \le 6 时的暴力枚举是常数级。- 空间复杂度O(n)。
