根据搜索结果，LeetCode 3901「好子序列查询」的 Go 实现如下：
---
思路
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。
---
Go 实现
```go
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
}
```
---
复杂度
- 时间复杂度：O((n + q) \times \log n)，其中 n \le 6 时的暴力枚举是常数级。
- 空间复杂度：O(n)。
