2025-11-18：分割数组后不同质数的最大数目。用go语言，给定一个长度为 n 的整数数组 nums 和若干查询，每个查询由
【摘要】 2025-11-18：分割数组后不同质数的最大数目。用go语言，给定一个长度为 n 的整数数组 nums 和若干查询，每个查询由一对整数 queries[i] = [idx, val] 表示。对每一次查询，先把 nums[idx] 改为 val（这个修改会影响后续的查询）。然后你可以在 1 到 n-1 之间选一个分割点 k，把数组分成不为空的前半段 nums[0…k-1] 和后半段 nums...
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 <= n == nums.length <= 5 * 10000。
1 <= queries.length <= 5 * 10000。
1 <= nums[i] <= 100000。
0 <= queries[i][0] < nums.length。
1 <= queries[i][1] <= 100000。
输入: 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. 预处理阶段：质数判断准备
- 埃拉托斯特尼筛法预处理：首先使用埃拉托斯特尼筛法预计算1到100,000（常数
mx = 1e5）范围内所有数字的质数状态。结果存储在布尔数组np中，np[i]为true表示i不是质数。这使得后续质数判断可在O(1)时间内完成。 - 初始化数据结构：
- 创建一个映射
pos，键为质数值，值为红黑树（Red-Black Tree），用于存储该质数在数组nums中出现的所有索引位置。红黑树支持高效插入、删除和查询最值操作。 - 初始化一个懒惰线段树（Lazy Segment Tree），大小为数组长度
n，初始值全为0。该线段树用于维护每个可能分割点k对应的"额外收益"。
- 创建一个映射
2. 初始化数据结构
- 遍历初始数组：对于数组
nums的每个元素：- 若元素是质数（通过
np数组检查），将其索引加入对应质数值的红黑树中。
- 若元素是质数（通过
- 构建线段树初始状态：对于每个出现至少两次的质数（即其红黑树大小 > 1）：
- 设该质数在数组中的最小索引为
L，最大索引为R。 - 在线段树的区间
[L, R]上执行加1操作。这表示若分割点k落在L和R之间（含端点），该质数会同时出现在前后两段，从而为总贡献带来+1的"额外收益"。
- 设该质数在数组中的最小索引为
3. 处理每个查询
对于每个查询queries[i] = [idx, val]：
- 更新数组值：将
nums[idx]修改为新值val。 - 处理旧值（若为质数）：
- 从旧值对应的红黑树中移除索引
idx。 - 若移除后该红黑树为空，则从映射
pos中删除此质数。 - 若红黑树非空（即该质数仍存在），更新线段树：
- 设当前最小索引为
L，最大索引为R。 - 根据被移除的索引
idx与L、R的关系，调整线段树区间：- 若
idx是唯一索引（L == R），更新区间[min(L, idx), max(R, idx)]，值减1。 - 若
idx < L，更新区间[idx, L-1]，值减1。 - 若
idx > R，更新区间[R+1, idx]，值减1。
- 若
- 此操作确保线段树准确反映该质数当前索引范围对分割点的影响。
- 设当前最小索引为
- 从旧值对应的红黑树中移除索引
- 处理新值（若为质数）：
- 若新值
val不在pos中，为其新建一个红黑树。 - 将索引
idx加入val对应的红黑树。 - 若红黑树大小 > 1（即该质数现多次出现），更新线段树：
- 逻辑同旧值处理，但执行加1操作，以添加新索引带来的影响。
- 若新值
- 计算当前查询的答案：
- 当前数组中不同质数的总数 =
len(pos)。 - 查询线段树整个区间
[0, n-1]的最大值，该值表示所有可能分割点k中，能同时使最多质数出现在两段中的"额外收益"最大值。 - 答案 =
len(pos) + 线段树最大值。这是因为总分由两部分组成：- 基础值：不同质数总数（每个质数至少贡献1）。
- 额外收益：若分割点使某个质数同时出现在两段，则该质数多贡献1。
- 当前数组中不同质数的总数 =
4. 关键点说明
- 分割点选择：分割点
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)（忽略常数项）。
该算法通过结合筛法、红黑树和线段树，高效处理了动态数组下的最优分割问题。
Go完整代码如下：
package main
import (
"fmt"
"math/bits"
"github.com/emirpasic/gods/v2/trees/redblacktree"
)
// import "github.com/emirpasic/gods/v2/trees/redblacktree"
const mx int = 1e5
var np = [mx + 1]bool{true, true}
func init() {
for i := 2; i <= mx; i++ {
if !np[i] {
for j := i * i; j <= mx; j += i {
np[j] = true
}
}
}
}
type lazySeg []struct {
l, r int
mx int
todo int
}
func mergeInfo(a, b int) int {
return max(a, b)
}
const todoInit = 0
func mergeTodo(f, old int) int {
return f + old
}
func (t lazySeg) apply(o int, f int) {
cur := &t[o]
cur.mx += f
cur.todo = mergeTodo(f, cur.todo)
}
func (t lazySeg) maintain(o int) {
t[o].mx = mergeInfo(t[o<<1].mx, t[o<<1|1].mx)
}
func (t lazySeg) spread(o int) {
f := t[o].todo
if f == todoInit {
return
}
t.apply(o<<1, f)
t.apply(o<<1|1, f)
t[o].todo = todoInit
}
func (t lazySeg) build(a []int, o, l, r int) {
t[o].l, t[o].r = l, r
t[o].todo = todoInit
if l == r {
t[o].mx = a[l]
return
}
m := (l + r) >> 1
t.build(a, o<<1, l, m)
t.build(a, o<<1|1, m+1, r)
t.maintain(o)
}
func (t lazySeg) update(o, l, r int, f int) {
if l <= t[o].l && t[o].r <= r {
t.apply(o, f)
return
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if l <= m {
t.update(o<<1, l, r, f)
}
if m < r {
t.update(o<<1|1, l, r, f)
}
t.maintain(o)
}
func (t lazySeg) query(o, l, r int) int {
if l <= t[o].l && t[o].r <= r {
return t[o].mx
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if r <= m {
return t.query(o<<1, l, r)
}
if l > m {
return t.query(o<<1|1, l, r)
}
return mergeInfo(t.query(o<<1, l, r), t.query(o<<1|1, l, r))
}
func newLazySegmentTreeWithArray(a []int) lazySeg {
n := len(a)
t := make(lazySeg, 2<<bits.Len(uint(n-1)))
t.build(a, 1, 0, n-1)
return t
}
func newLazySegmentTree(n int, initVal int) lazySeg {
a := make([]int, n)
for i := range a {
a[i] = initVal
}
return newLazySegmentTreeWithArray(a)
}
func maximumCount(nums []int, queries [][]int) (ans []int) {
n := len(nums)
pos := map[int]*redblacktree.Tree[int, struct{}]{}
for i, x := range nums {
if np[x] {
continue
}
if _, 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)
} else if i < l {
t.update(1, i, l-1, delta)
} else if 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)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from sortedcontainers import SortedSet
import math
mx = 10**5
np = [False] * (mx + 1)
np[0] = np[1] = True
# 质数筛
for i in range(2, mx + 1):
if not np[i]:
for j in range(i*i, mx + 1, i):
np[j] = True
# -------------------------------
# 懒标记线段树：区间加 + 区间最大值
# -------------------------------
class LazySegTree:
def __init__(self, a):
n = len(a)
size = 1 << (n - 1).bit_length()
self.n = n
self.size = size
self.mx = [0] * (size * 2)
self.todo = [0] * (size * 2) # lazy tag
# build
# leaves
for i in range(n):
self.mx[size + i] = a[i]
for i in range(size - 1, 0, -1):
self.mx[i] = max(self.mx[i << 1], self.mx[i << 1 | 1])
def apply(self, o, f):
self.mx[o] += f
self.todo[o] += f
def push(self, o):
f = self.todo[o]
if f != 0:
self.apply(o << 1, f)
self.apply(o << 1 | 1, f)
self.todo[o] = 0
def update(self, l, r, f, o=1, L=0, R=None):
if R is None:
R = self.size - 1
if l <= L and R <= r:
self.apply(o, f)
return
if R < l or r < L:
return
self.push(o)
mid = (L + R) // 2
self.update(l, r, f, o << 1, L, mid)
self.update(l, r, f, o << 1 | 1, mid + 1, R)
self.mx[o] = max(self.mx[o << 1], self.mx[o << 1 | 1])
def query(self, l, r, o=1, L=0, R=None):
if R is None:
R = self.size - 1
if l <= L and R <= r:
return self.mx[o]
if R < l or r < L:
return -10**18
self.push(o)
mid = (L + R) // 2
return max(self.query(l, r, o << 1, L, mid),
self.query(l, r, o << 1 | 1, mid + 1, R))
# -------------------------------
# main logic
# -------------------------------
def maximumCount(nums, queries):
n = len(nums)
# 每个质数值对应一个 SortedSet（模拟 red-black-tree）
pos = {}
for i, x in enumerate(nums):
if np[x]:
continue
if x not in pos:
pos[x] = SortedSet()
pos[x].add(i)
# 初始线段树，全 0
t = LazySegTree([0] * n)
# 对每个质数值，若出现两次以上，则区间加 1
for ps in pos.values():
if len(ps) > 1:
l, r = ps[0], ps[-1]
t.update(l, r, 1)
def update(ps, i, delta):
l, r = ps[0], ps[-1]
if l == r:
L = min(l, i)
R = max(r, i)
t.update(L, R, delta)
elif i < l:
t.update(i, l - 1, delta)
elif i > r:
t.update(r + 1, i, delta)
ans = []
for i, v in queries:
old = nums[i]
nums[i] = v
# 删除旧值
if not np[old]:
ps = pos[old]
ps.remove(i)
if len(ps) == 0:
del pos[old]
else:
update(ps, i, -1)
# 插入新值
if not np[v]:
if v not in pos:
pos[v] = SortedSet()
else:
update(pos[v], i, 1)
pos[v].add(i)
# 输出结果
ans.append(len(pos) + t.query(0, n - 1))
return ans
# -------------------------------
# 测试
# -------------------------------
if __name__ == "__main__":
nums = [2, 1, 3, 1, 2]
queries = [[1, 2], [3, 3]]
print(maximumCount(nums, queries))
C++完整代码如下：
#include <bits/stdc++.h>
using namespace std;
const int MX = 100000;
bool np[MX + 1]; // 非质数标记
struct Node {
int l, r;
int mx;
int todo;
};
struct LazySeg {
vector<Node> t;
int n;
LazySeg(int n, int initVal) : n(n) {
int size = 2 << (32 - __builtin_clz(n - 1));
t.resize(size);
vector<int> a(n, initVal);
build(a, 1, 0, n - 1);
}
void build(vector<int>& a, int o, int l, int r) {
t[o].l = l; t[o].r = r;
t[o].todo = 0;
if (l == r) {
t[o].mx = a[l];
return;
}
int m = (l + r) >> 1;
build(a, o << 1, l, m);
build(a, o << 1 | 1, m + 1, r);
t[o].mx = max(t[o << 1].mx, t[o << 1 | 1].mx);
}
void apply(int o, int f) {
t[o].mx += f;
t[o].todo += f;
}
void spread(int o) {
int f = t[o].todo;
if (f == 0) return;
apply(o << 1, f);
apply(o << 1 | 1, f);
t[o].todo = 0;
}
void update(int o, int l, int r, int f) {
if (l <= t[o].l && t[o].r <= r) {
apply(o, f);
return;
}
spread(o);
int m = (t[o].l + t[o].r) >> 1;
if (l <= m) update(o << 1, l, r, f);
if (m < r) update(o << 1 | 1, l, r, f);
t[o].mx = max(t[o << 1].mx, t[o << 1 | 1].mx);
}
int query(int o, int l, int r) {
if (l <= t[o].l && t[o].r <= r) {
return t[o].mx;
}
spread(o);
int m = (t[o].l + t[o].r) >> 1;
if (r <= m) return query(o << 1, l, r);
if (l > m) return query(o << 1 | 1, l, r);
return max(query(o << 1, l, r), query(o << 1 | 1, l, r));
}
};
vector<int> maximumCount(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
unordered_map<int, map<int,int>> pos;
for (int i = 0; i <= MX; i++) np[i] = false;
np[0] = np[1] = true;
for (int i = 2; i * i <= MX; i++)
if (!np[i])
for (int j = i * i; j <= MX; j += i)
np[j] = true;
for (int i = 0; i < n; i++) {
int x = nums[i];
if (!np[x]) pos[x][i] = 1;
}
LazySeg t(n, 0);
for (auto &p : pos) {
auto &mp = p.second;
if (mp.size() > 1) {
int l = mp.begin()->first;
int r = mp.rbegin()->first;
t.update(1, l, r, 1);
}
}
auto update = [&](map<int,int>& mp, int i, int delta) {
int l = mp.begin()->first;
int r = mp.rbegin()->first;
if (l == r) {
t.update(1, min(l, i), max(r, i), delta);
} else if (i < l) {
t.update(1, i, l - 1, delta);
} else if (i > r) {
t.update(1, r + 1, i, delta);
}
};
vector<int> ans;
for (auto &q : queries) {
int i = q[0], v = q[1];
int old = nums[i];
nums[i] = v;
if (!np[old]) {
auto& mp = pos[old];
mp.erase(i);
if (mp.empty()) {
pos.erase(old);
} else {
update(mp, i, -1);
}
}
if (!np[v]) {
auto &mp = pos[v];
if (!mp.empty()) update(mp, i, 1);
mp[i] = 1;
}
ans.push_back((int)pos.size() + t.query(1, 0, n - 1));
}
return ans;
}
int main() {
vector<int> nums = {2, 1, 3, 1, 2};
vector<vector<int>> queries = {{1, 2}, {3, 3}};
vector<int> result = maximumCount(nums, queries);
for (int x : result) cout << x << " ";
cout << endl;
return 0;
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）