Kimi LeetCode 3901. 好子序列查询 Python3实现
根据搜索结果，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 实现
```python
from math import gcd
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
```
---
复杂度
- 时间复杂度：O((n + q) \times \log n)，其中 n \le 6 时的暴力枚举是常数级。
- 空间复杂度：O(n)。