#3569
Maximize Count of Distinct Primes After Split
hard · 18.4% accepted · 24 likes · top 1%
array · math · segment tree · number theory
Description
You are given an integer array nums having length n and a 2D integer array queries where queries[i] = [idx, val].
For each query:
- Update nums[idx] = val.
- Choose an integer k with 1 <= k < n to split the array into the non-empty prefix nums[0..k-1] and suffix nums[k..n-1] such that the sum of the counts of distinct prime values in each part is maximum.
Note: The changes made to the array in one query persist into the next query.
Return an array containing the result for each query, in the order they are given.
Solution