### PROBLEM LINK:

**Author:** Kirill

**Tester:** Praveen Dhinwa

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

Medium

### PREREQUISITES:

### PROBLEM:

Given an array of numbers A, support the following two queries:

- for a given range [L, R], reduce each number in A[L…R] by its smallest prime factor,
- for a given range [L, R], find the number in A[L…R] with largest smallest prime factor.

### QUICK EXPLANATION:

Use a segment tree while maintaining the segments in which each number is equal to one.

### EXPLANATION:

We are given an array A of size N, and we are supposed to maintain two kind of range queries on this array:

- Update the numbers in a range A[L…R].
- Query some information about the numbers in the range A[L…R].

Let us first solve a simpler version of the problem, in which we support the following queries, and then we will come back to the original problem:

- Update a number A[x]
- Query some information about the numbers in the range A[L…R].

This seems like a classical segment tree problem. We can create a segment tree for the array. As explained here in the segment tree each node maintains some information about the elements A[k * 2^x, (k + 1) * 2^x). In our case, this information would be the largest smallest prime factor of the numbers in the range.

struct info { // The node corresponds to A[low..high] int low; int high; // The largest value of the smallest prime factors // of the number in A[low..high]. int value; // The children nodes of this node containing // information about the ranges // [low, mid], and [mid + 1, high]. info* left; info* right; };

Once we update a number A[x], the information in all nodes containing the index x will be updated. There are at most O (lg N) such nodes, hence the update operation can be done in O (lg N) time. For the query operation about the range [L, R], we find the list of nodes whose ranges is contained in [L, R], and take the maximum of their values. Once again, there are O (lg N) such nodes, hence the query operation can also be implemented in O (lg N) time. For the implementation details of update and query, please see here.

Now, let us see how we could solve the original problem. One possibility could be that, when we get the range modification entry, we modify each element in the range one by one, and hence perform (R - L + 1) single element update queries. This approach would be to slow, as it makes the complexity of range update query to O ((R - L + 1) lg N). Next, we discuss that many of these single element update queries can be ignored, and the number of actual performed queries is much lower.

Note that, if the value of an element A[x] is 1, then update query on A[x] does not have any effect on the segment tree. We call such queries as degenerate queries, and can discard them. Also note that a number M can be written as a product of at most O (lg M) prime numbers, Hence, we can perform at most O (lg M) non-degenerate modification queries on A[x] = M, all the latter queries will be degenerate. This means that if all numbers in the array are smaller than M, then a most O (N lg M) non-degenerate single element update queries would be performed. Each single element update query takes O (lg N) time, and hence all update queries can be performed in O (N lg M lg N) time.

However, now the problem is how to find the non-degenerate single element update queries for the range [L, R]. For this purpose, we maintain another information in the segment tree node, which is the number of elements in the range which are larger than one.

The following snippet shows how to use this information so that we only perform single element update queries, without iterating through all elements in the range. The idea is similar to the lazy propagation.

struct info { // The node corresponds to A[low..high] int low; int high; // Number of elements in A[low..high], which are larger than 1. int count_non_degenerate; // The largest value of the smallest prime factors // of the number in A[low..high]. int value; // The children nodes of this node containing // information about the ranges // [low, mid], and [mid + 1, high]. info* left; info* right; };

Now, while performing the range modification query, we can discard all subranges which have all elements equal to one.

void update (info* nd, int L, int R) { // This node has a range disjoint with [L, R] if (nd->low > R || L > nd->high) continue; // All elements in this range are 1, nothing to do. if (nd->count_non_degenerate == 0) continue; if (nd->low == nd->high) { // Perform the single element update query ... return; } update(nd->left, L, R); update(nd->right, L, R); }

This means all the range update queries can be performed in O (N lg M lg N), while the range query time is O (lg N) per range.

### TIME COMPLEXITY:

O (N lg M lg N + Q lg N), where N is the size of the array, M is the bound on the elements of the array, and Q is the number of queries.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution

Tester’s solution will be uploaded soon.