3569. Maximize Count of Distinct Primes After Split

Hard

50 Points

Array

Math

Segment Tree

Number Theory

You are given an integer array nums having length n and a 2D integer array queries where queries[i] = [idx, val]. For each query: 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.

Examples

Example 1

Input: nums = [2,1,3,1,2], queries = [[1,2],[3,3]] Output: [3,4] Explanation:

Example 2

Input: nums = [2,1,4], queries = [[0,1]] Output: [0] Explanation:

Constraints

2 <= n == nums.length <= 5 * 104
1 <= queries.length <= 5 * 104
1 <= nums[i] <= 105
0 <= queries[i][0] < nums.length
1 <= queries[i][1] <= 105