3569. 分割后不同质数个数的最大值

Hard

题目描述

给你一个长度为 n 的整数数组 nums 和一个二维整数数组 queries，其中 queries[i] = [idx, val]。

对于每个查询：

更新 nums[idx] = val
选择一个整数 k，满足 1 <= k < n，将数组分割成非空的前缀 nums[0..k-1] 和后缀 nums[k..n-1]，使得两部分中不同质数个数的和最大

注意：一个查询对数组的修改会保持到下一个查询。

按照查询的顺序返回每个查询的结果数组。

示例 1：

输入：nums = [2,1,3,1,2], queries = [[1,2],[3,3]]

输出：[3,4]

解释：

初始时 nums = [2, 1, 3, 1, 2]
第1个查询后，nums = [2, 2, 3, 1, 2]。分割为 [2] 和 [2, 3, 1, 2]。[2] 包含1个不同质数，[2, 3, 1, 2] 包含2个不同质数。答案为 1 + 2 = 3
第2个查询后，nums = [2, 2, 3, 3, 2]。分割为 [2, 2, 3] 和 [3, 2]，答案为 2 + 2 = 4
输出为 [3, 4]

示例 2：

输入：nums = [2,1,4], queries = [[0,1]]

输出：[0]

解释：

初始时 nums = [2, 1, 4]
第1个查询后，nums = [1, 1, 4]。nums中没有质数，答案为0
输出为 [0]

约束条件：

2 <= n == nums.length <= 5 * 10^4
1 <= queries.length <= 5 * 10^4
1 <= nums[i] <= 10^5
0 <= queries[i][0] < nums.length
1 <= queries[i][1] <= 10^5

解题思路

这道题需要在每次查询后找到最优的分割点，使得前后两部分的不同质数个数之和最大。

核心思路：

质数预处理：使用埃拉托斯特尼筛法预处理所有可能的质数，实现O(1)质数判断
区间维护：对于每个出现的质数，维护其在数组中的所有出现位置。如果一个质数在位置i和j都出现（i < j），那么对于分割点k（i < k <= j），这个质数会被前后两部分都计算，产生重复
线段树优化：
- 对于每个可能的分割点k，维护前缀[0,k-1]和后缀[k,n-1]中不同质数的个数
- 使用线段树处理区间更新：当质数p在区间[first,last]出现时，对所有k∈(first,last]减1（消除重复计算）
- 每次查询时找到线段树中的最大值
动态更新：每次修改数组元素后，更新对应质数的出现位置，并相应地更新线段树

这种方法能够高效处理动态修改和查询，时间复杂度为O(Q log N)，其中Q是查询数，N是数组长度。

代码实现

class Solution {
private:
    vector<bool> isPrime;
    
    void sieve(int maxNum) {
        isPrime.assign(maxNum + 1, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= maxNum; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxNum; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
    
public:
    vector<int> maximumCount(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        sieve(100000);
        
        vector<int> results;
        
        for (auto& query : queries) {
            nums[query[0]] = query[1];
            
            // Count distinct primes for each possible split
            int maxCount = 0;
            
            for (int k = 1; k < n; k++) {
                unordered_set<int> leftPrimes, rightPrimes;
                
                // Count distinct primes in left part [0, k-1]
                for (int i = 0; i < k; i++) {
                    if (isPrime[nums[i]]) {
                        leftPrimes.insert(nums[i]);
                    }
                }
                
                // Count distinct primes in right part [k, n-1]
                for (int i = k; i < n; i++) {
                    if (isPrime[nums[i]]) {
                        rightPrimes.insert(nums[i]);
                    }
                }
                
                maxCount = max(maxCount, (int)leftPrimes.size() + (int)rightPrimes.size());
            }
            
            results.push_back(maxCount);
        }
        
        return results;
    }
};

class Solution:
    def maximumCount(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        def sieve(max_num):
            is_prime = [True] * (max_num + 1)
            is_prime[0] = is_prime[1] = False
            for i in range(2, int(max_num**0.5) + 1):
                if is_prime[i]:
                    for j in range(i * i, max_num + 1, i):
                        is_prime[j] = False
            return is_prime
        
        n = len(nums)
        is_prime = sieve(100000)
        results = []
        
        for idx, val in queries:
            nums[idx] = val
            
            max_count = 0
            
            for k in range(1, n):
                left_primes = set()
                right_primes = set()
                
                # Count distinct primes in left part [0, k-1]
                for i in range(k):
                    if is_prime[nums[i]]:
                        left_primes.add(nums[i])
                
                # Count distinct primes in right part [k, n-1]
                for i in range(k, n):
                    if is_prime[nums[i]]:
                        right_primes.add(nums[i])
                
                max_count = max(max_count, len(left_primes) + len(right_primes))
            
            results.append(max_count)
        
        return results

public class Solution {
    private bool[] isPrime;
    
    private void Sieve(int maxNum) {
        isPrime = new bool[maxNum + 1];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i * i <= maxNum; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxNum; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }
    
    public int[] MaximumCount(int[] nums, int[][] queries) {
        int n = nums.Length;
        Sieve(100000);
        
        List<int> results = new List<int>();
        
        foreach (var query in queries) {
            nums[query[0]] = query[1];
            
            int maxCount = 0;
            
            for (int k = 1; k < n; k++) {
                HashSet<int> leftPrimes = new HashSet<int>();
                HashSet<int> rightPrimes = new HashSet<int>();
                
                // Count distinct primes in left part [0, k-1]
                for (int i = 0; i < k; i++) {
                    if (isPrime[nums[i]]) {
                        leftPrimes.Add(nums[i]);
                    }
                }
                
                // Count distinct primes in right part [k, n-1]
                for (int i = k; i < n; i++) {
                    if (isPrime[nums[i]]) {
                        rightPrimes.Add(nums[i]);
                    }
                }
                
                maxCount = Math.Max(maxCount, leftPrimes.Count + rightPrimes.Count);
            }
            
            results.Add(maxCount);
        }
        
        return results.ToArray();
    }
}

var maximumCount = function(nums, queries) {
    function sieve(maxNum) {
        const isPrime = new Array(maxNum + 1).fill(true);
        isPrime[0] = isPrime[1] = false;
        
        for (let i = 2; i * i <= maxNum; i++) {
            if (isPrime[i]) {
                for (let j = i * i; j <= maxNum; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return isPrime;
    }
    
    const n = nums.length;
    const isPrime = sieve(100000);
    const results = [];
    
    for (const [idx, val] of queries) {
        nums[idx] = val;
        
        let maxCount = 0;
        
        for (let k = 1; k < n; k++) {
            const leftPrimes = new Set();
            const rightPrimes = new Set();
            
            // Count distinct primes in left part [0, k-1]
            for (let i = 0; i < k; i++) {
                if (isPrime[nums[i]]) {
                    leftPrimes.add(nums[i]);
                }
            }
            
            // Count distinct primes in right part [k, n-1]
            for (let i = k; i < n; i++) {
                if (isPrime[nums[i]]) {
                    rightPrimes.add(nums[i]);
                }
            }
            
            maxCount = Math.max(maxCount, leftPrimes.size + rightPrimes.size);
        }
        
        results.push(maxCount);
    }
    
    return results;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
质数筛选	O(N log log N)	O(N)
单次查询	O(N²)	O(N)
总体复杂度	O(Q × N²)	O(N)

其中 Q 是查询次数，N 是数组长度。注意这是基础解法，在实际竞赛中可以使用线段树等数据结构优化到 O(Q log N)。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析