摘要：2025-11-18：分割数组后不同质数的最大数目。用go语言，给定一个长度为 n 的整数数组 nums 和若干查询，每个查询由一对整数 queries[i] = [idx, val] 表示。
2025-11-18：分割数组后不同质数的最大数目。用go语言，给定一个长度为 n 的整数数组 nums 和若干查询，每个查询由一对整数 queries[i] = [idx, val] 表示。
对每一次查询，先把 nums[idx] 改为 val（这个修改会影响后续的查询）。然后你可以在 1 到 n-1 之间选一个分割点 k，把数组分成不为空的前半段 nums[0..k-1] 和后半段 nums[k..n-1]。对于每一段，统计其中不同的质数的个数（质数指大于 1 且只有 1 和自身两个约数的正整数），将前后两段的这两个计数相加。你需要选取使这个和尽可能大的分割点 k。
返回一个长度与查询数相同的数组，按查询顺序给出每次操作后能得到的最大和。
2
1
1
0
1
输入: nums = [2,1,3,1,2], queries = [[1,2],[3,3]]。
输出: [3,4]。
解释:
初始时 nums = [2, 1, 3, 1, 2]。
在第一次查询后，nums = [2, 2, 3, 1, 2]。将 nums 分为 [2] 和 [2, 3, 1, 2]。[2] 包含 1 个不同的质数，[2, 3, 1, 2] 包含 2 个不同的质数。所以此查询的答案是 1 + 2 = 3。
在第二次查询后，nums = [2, 2, 3, 3, 2]。将 nums 分为 [2, 2, 3] 和 [3, 2]，其答案为 2 + 2 = 4。
最终输出为 [3, 4]。
题目来自力扣3569。
以下是对给定Go代码处理"分割数组后不同质数的最大数目"问题的详细分步描述。算法核心在于动态维护数组状态，并通过高效数据结构快速计算每次更新后的最优分割点。
• 埃拉托斯特尼筛法预处理：首先使用埃拉托斯特尼筛法预计算1到100,000（常数mx = 1e5）范围内所有数字的质数状态。结果存储在布尔数组np中，np[i]为true表示i不是质数。这使得后续质数判断可在O(1)时间内完成。
• 初始化数据结构：
创建一个映射pos，键为质数值，值为红黑树（Red-Black Tree），用于存储该质数在数组nums中出现的所有索引位置。红黑树支持高效插入、删除和查询最值操作。初始化一个懒惰线段树（Lazy Segment Tree），大小为数组长度n，初始值全为0。该线段树用于维护每个可能分割点k对应的"额外收益"。若元素是质数（通过np数组检查），将其索引加入对应质数值的红黑树中。• 构建线段树初始状态：对于每个出现至少两次的质数（即其红黑树大小 > 1）：
设该质数在数组中的最小索引为L，最大索引为R。在线段树的区间[L, R]上执行加1操作。这表示若分割点k落在L和R之间（含端点），该质数会同时出现在前后两段，从而为总贡献带来+1的"额外收益"。• 更新数组值：将nums[idx]修改为新值val。
• 处理旧值（若为质数）：
从旧值对应的红黑树中移除索引idx。若移除后该红黑树为空，则从映射pos中删除此质数。若红黑树非空（即该质数仍存在），更新线段树：设当前最小索引为L，最大索引为R。根据被移除的索引idx与L、R的关系，调整线段树区间：若idx是唯一索引（L == R），更新区间[min(L, idx), max(R, idx)]，值减1。若idx 若idx > R，更新区间[R+1, idx]，值减1。此操作确保线段树准确反映该质数当前索引范围对分割点的影响。• 处理新值（若为质数）：
若新值val不在pos中，为其新建一个红黑树。将索引idx加入val对应的红黑树。若红黑树大小 > 1（即该质数现多次出现），更新线段树：逻辑同旧值处理，但执行加1操作，以添加新索引带来的影响。• 计算当前查询的答案：
当前数组中不同质数的总数 = len(pos)。查询线段树整个区间[0, n-1]的最大值，该值表示所有可能分割点k中，能同时使最多质数出现在两段中的"额外收益"最大值。答案 = len(pos) + 线段树最大值。这是因为总分由两部分组成：基础值：不同质数总数（每个质数至少贡献1）。额外收益：若分割点使某个质数同时出现在两段，则该质数多贡献1。• 分割点选择：分割点k取值范围为1到n-1，线段树自动维护每个k对应的收益，无需显式遍历所有k。
• 懒惰线段树的作用：支持区间加减和区间最大值查询，均可在O(log n)时间内完成，确保高效性。
• 红黑树的作用：快速获取质数索引的最小值/最大值，并在索引变化时动态维护。
• 预处理：
埃拉托斯特尼筛法：O(mx log log mx) ≈ O(10^5 log log 10^5)，可视为常数时间。初始化红黑树和线段树：O(n log n)。• 每个查询处理：
红黑树插入/删除：O(log n)。线段树更新：O(log n)。线段树查询最大值：O(1)（直接访问根节点值）。• 总体：O(n log n + q log n)，其中n为数组长度，q为查询数量。
• 筛法数组：O(mx) = O(10^5)，常数空间。
• 红黑树映射：最坏情况下存储O(n)个索引。
• 线段树：O(n)空间。
• 总体：O(n)（忽略常数项）。
该算法通过结合筛法、红黑树和线段树，高效处理了动态数组下的最优分割问题。
package mainimport ( "fmt" "math/bits" "github.com/emirpasic/gods/v2/trees/redblacktree")const mx int = 1e5var np = [mx + 1]bool{true, true}func init { for i := 2; i > 1 t.build(a, o> 1 if l > 1 if r m { return t.query(oif _, ok := pos[x]; !ok { pos[x] = redblacktree.New[int, struct{}] } pos[x].Put(i, struct{}{}) } t := newLazySegmentTree(n, 0) for _, ps := range pos { if ps.Size > 1 { t.update(1, ps.Left.Key, ps.Right.Key, 1) } } update := func(ps *redblacktree.Tree[int, struct{}], i, delta int) { l, r := ps.Left.Key, ps.Right.Key if l == r { t.update(1, min(l, i), max(r, i), delta) } elseif i r { t.update(1, r+1, i, delta) } } for _, q := range queries { i, v := q[0], q[1] old := nums[i] nums[i] = v // 处理旧值 if !np[old] { ps := pos[old] ps.Remove(i) if ps.Empty { delete(pos, old) } else { update(ps, i, -1) } } // 处理新值 if !np[v] { if ps, ok := pos[v]; !ok { pos[v] = redblacktree.New[int, struct{}] } else { update(ps, i, 1) } pos[v].Put(i, struct{}{}) } // 整个数组的不同质数个数 + 切一刀的最大额外收益 ans = append(ans, len(pos)+t.query(1, 0, n-1)) } return } func main { nums := int{2, 1, 3, 1, 2} queries := int{{1, 2}, {3, 3}} result := maximumCount(nums, queries) fmt.Println(result) }我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
·
来源：湖南教育网资讯
