#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