Maximize Count of Distinct Primes After Split

• Pre-compute prime factors for all numbers up to the maximum possible value using a Sieve of Eratosthenes.
• For each query [idx, val]:
  1. Update the array: nums[idx] = val.
  2. Initialize a variable max_score to 0.
  3. Iterate through all possible split points k from 1 to n-1.
  4. For each k: a. Calculate the number of distinct prime factors in the prefix nums[0...k-1]. This involves creating a set, iterating through the prefix elements, finding their prime factors, and adding them to the set. The size of the set is the count for the prefix. b. Similarly, calculate the number of distinct prime factors for the suffix nums[k...n-1]. c. The score for the split k is the sum of the two counts. d. Update max_score = max(max_score, score).
  5. After checking all k, the max_score is the result for the current query. Add it to the results array.

The core of this method is a nested loop structure for each query. The outer loop iterates through all valid split points k from 1 to n-1. The inner loops are responsible for calculating the distinct prime counts. To do this, we use a HashSet to keep track of unique prime factors. For a given prefix nums[0...k-1], we iterate from i=0 to k-1, find all prime factors of nums[i], and add them to a prefix_primes set. The size of this set gives the count. We do the same for the suffix nums[k...n-1]. This entire process is repeated for every single query.

1// PrimeHandler class for Sieve and factorization is assumed to exist.2PrimeHandler primeHandler = new PrimeHandler();3 4// Inside the main method, for each query:5// nums is updated with queries[i][1] at index queries[i][0]6 7int maxScore = 0;8int n = nums.length;9for (int k = 1; k < n; k++) {10    // Calculate distinct primes in prefix nums[0...k-1]11    Set<Integer> prefixPrimes = new HashSet<>();12    for (int i = 0; i < k; i++) {13        prefixPrimes.addAll(primeHandler.getPrimeFactors(nums[i]));14    }15 16    // Calculate distinct primes in suffix nums[k...n-1]17    Set<Integer> suffixPrimes = new HashSet<>();18    for (int i = k; i < n; i++) {19        suffixPrimes.addAll(primeHandler.getPrimeFactors(nums[i]));20    }21 22    maxScore = Math.max(maxScore, prefixPrimes.size() + suffixPrimes.size());23}24// maxScore is the answer for the current query.

• Pre-compute prime factors using a Sieve.
• For each query [idx, val]:
  1. Update nums[idx] = val.
  2. Create a prefix_counts array of size n+1. Populate it by iterating from k=1 to n. For each k, calculate the distinct prime count in nums[0...k-1] by adding the prime factors of nums[k-1] to a running set of primes.
  3. Create a suffix_counts array of size n+1. Populate it by iterating from k=n-1 down to 0. For each k, calculate the distinct prime count in nums[k...n-1] by adding factors of nums[k] to a running set.
  4. Initialize max_score = 0.
  5. Iterate k from 1 to n-1: a. The score for the split is prefix_counts[k] + suffix_counts[k]. b. Update max_score = max(max_score, score).
  6. Store max_score as the answer for the query.

For each query, after the array update, we first build an array prefix_counts. prefix_counts[k] will store the number of distinct prime factors in nums[0...k-1]. This can be computed efficiently in a single pass from left to right, maintaining a running HashSet of primes. Similarly, we build a suffix_counts array where suffix_counts[k] stores the count for nums[k...n-1], which is done with a pass from right to left. Once we have these two arrays, we can find the score for any split k in O(1) time by summing prefix_counts[k] and suffix_counts[k]. A final loop over k finds the maximum possible score.

1// PrimeHandler class is assumed to exist.2PrimeHandler primeHandler = new PrimeHandler();3 4// Inside the main method, for each query:5// nums is updated.6int n = nums.length;7 8// Pre-calculate all prefix counts9int[] prefixCounts = new int[n + 1];10Set<Integer> currentPrefixPrimes = new HashSet<>();11for (int k = 1; k <= n; k++) {12    currentPrefixPrimes.addAll(primeHandler.getPrimeFactors(nums[k - 1]));13    prefixCounts[k] = currentPrefixPrimes.size();14}15 16// Pre-calculate all suffix counts17int[] suffixCounts = new int[n + 1];18Set<Integer> currentSuffixPrimes = new HashSet<>();19for (int k = n - 1; k >= 0; k--) {20    currentSuffixPrimes.addAll(primeHandler.getPrimeFactors(nums[k]));21    suffixCounts[k] = currentSuffixPrimes.size();22}23 24// Find the best split25int maxScore = 0;26for (int k = 1; k < n; k++) {27    // Score for split at k is count for prefix nums[0...k-1] and suffix nums[k...n-1]28    int score = prefixCounts[k] + suffixCounts[k];29    maxScore = Math.max(maxScore, score);30}31// maxScore is the answer for the current query.

• Preprocessing:
  1. Use a Sieve to find the Smallest Prime Factor (SPF) for all numbers up to 10^5.
  2. Create a map occurrences where occurrences[p] is a sorted set of indices i where p is a prime factor of nums[i].
  3. Calculate total_distinct_primes, the total number of unique primes across the entire array.
• Data Structure:
  1. Use a Segment Tree with Lazy Propagation over the range of split points k from 1 to n-1. This tree will support range additions and range maximum queries.
• Initialization:
  1. The score for a split k is total_distinct_primes + |P_prefix ∩ P_suffix|. We need to maximize the size of the intersection, which we call overlap(k).
  2. A prime p contributes to overlap(k) if its first occurrence f is < k and its last occurrence l is >= k. This is true for k in the range [f+1, l].
  3. For each prime p that appears more than once, perform a range update on the segment tree, adding 1 to the range [f+1, l].
• Per Query:
  1. For an update nums[idx] = val, identify the prime factors of the old and new values (P_old, P_new).
  2. For each prime p in P_old ∪ P_new: a. Undo: If p had multiple occurrences before, find its old first and last indices (f, l) and subtract 1 from the range [f+1, l] in the segment tree. b. Update: Modify occurrences[p] by removing/adding idx. Update total_distinct_primes if the set of occurrences for p becomes empty or non-empty. c. Redo: If p has multiple occurrences now, find its new first and last indices (f', l') and add 1 to the range [f'+1, l'] in the segment tree.
  3. After processing all affected primes, query the segment tree for the maximum value, max_overlap.
  4. The answer for the query is total_distinct_primes + max_overlap.

We maintain the first and last occurrence indices for each prime. A prime p with first occurrence f and last l contributes to the intersection (overlap) for all splits k where f < k <= l. This means for each such prime, we can think of it as adding +1 to an 'overlap score' for all k in the range [f+1, l]. A segment tree with lazy propagation is perfect for this: it can handle range additions and find the maximum value in a range efficiently.

When nums[idx] is updated, only the prime factors of the old and new values are affected. For each such prime, we find its first and last occurrences before the change, undo its contribution on the segment tree (a range update of -1), update its set of occurrences, and then apply its new contribution (a range update of +1 based on new first and last indices). The total number of distinct primes is also tracked separately. The final answer for a query is this total count plus the maximum overlap score queried from the segment tree.

1// Segment Tree with lazy propagation for range add and range max query2class SegmentTree { /* ... standard implementation ... */ }3 4// Main logic for a query5void processQuery(int idx, int val) {6    int oldVal = nums[idx];7    Set<Integer> oldPrimes = primeHandler.getPrimeFactors(oldVal);8    Set<Integer> newPrimes = primeHandler.getPrimeFactors(val);9 10    Set<Integer> affectedPrimes = new HashSet<>(oldPrimes);11    affectedPrimes.addAll(newPrimes);12 13    for (int p : affectedPrimes) {14        TreeSet<Integer> occs = occurrences.get(p);15        // 1. Undo old contribution16        if (occs != null && occs.size() > 1) {17            int oldFirst = occs.first();18            int oldLast = occs.last();19            segTree.rangeUpdate(oldFirst + 1, oldLast, -1);20        }21 22        // 2. Update occurrences and totalDistinctPrimes23        if (oldPrimes.contains(p)) {24            if (occs.size() == 1) totalDistinctPrimes--;25            occs.remove(idx);26        }27        if (newPrimes.contains(p)) {28            if (occs == null) {29                occs = new TreeSet<>();30                occurrences.put(p, occs);31            }32            if (occs.isEmpty()) totalDistinctPrimes++;33            occs.add(idx);34        }35 36        // 3. Add new contribution37        if (occs != null && occs.size() > 1) {38            int newFirst = occs.first();39            int newLast = occs.last();40            segTree.rangeUpdate(newFirst + 1, newLast, 1);41        }42    }43    nums[idx] = val;44 45    int maxOverlap = segTree.queryMax(1, n - 1);46    int result = totalDistinctPrimes + Math.max(0, maxOverlap);47    // Add result to answer list48}