### PROBLEM LINK:

* Author:* Bharat Goyal

* Tester:* Shashwat Chandra, Taranpreet Singh, Bharat Goyal

* Editorialist:* Bharat Goyal

### DIFFICULTY

Easy-Medium

### PROBLEM

Given an array A partition it into the minimum number of chains such that for members A_i and A_{i+1} of the same chain, A_{i+1} \bmod A_i = 0. You have to process Q point updates and queries. The queries ask for the first element of the chain to which the provided index belongs.

### PREREQUISITES

C++ Sets, observations.

### QUICK EXPLANATION:

When no two adjacent elements are equal, each chain is guaranteed to have length smaller than log_2(Z) (Z is the maximum value in the array). For the second subtask, we can compress each group of adjacent positions that have the same element by using a set. This way, the length of each chain once again becomes log_2(Z).

### EXPLANATION:

#### Subtask 1:

Note that no two elements can be adjacent and equal. This means for a given chain B_1, B_2 â€¦ B_k , the condition \frac{B_{j+1} }{ B_j } \geq2 holds for any j \leq k-1 . From this we can infer that the length of any chain will be at most log_2(Z) where Z represents the maximum value of the array elements (10^6). So, for the update operation, we can change the values in the original array and for the queries, we can start from the given index and keep on moving to the previous index until we enter a different chain. Note that we donâ€™t have to store the chains separately. Whether or not two elements are in the same chain can be verified by applying the modulo condition given in the question.

#### Subtask 2:

There are two ways to handle this subtask. The first way would be to compress all adjacent equal values into one chain and then handle the queries like we did in subtask 1. For this solution, we push the first index at which a particular value occurs into a set (and then the adjacent occurrences of the same value need not be added to the set). The update operation becomes a bit tricky here. Let ind represent the index whose value is being updated and val be itâ€™s new value. The following cases have to be handled:

In case val is not the same as A_{ind+1} we append ind+1 to the set.

If val is the same as A_{ind+1} we remove ind+1 from the set.

If val is not equal to A_{ind-1} then we add ind to the set.

If val is equal to A_{ind-1}, we must ensure that ind is removed from the set.

For the queries, we can use a set iterator and decrement it until we find the first element of the chain. Since weâ€™re using sets to ensure that we donâ€™t iterate over duplicate elements, this step is guaranteed to be O(log_2Z) (Z is the maximum value present in the array).

#### Subtask 2 (Alternative):

The second way to handle this subtask is to store the index of the first element of each chain in the set. If we are able to maintain this set, then the answer to each query will simply be the largest index in the set that is smaller than or equal to the query index. The initial set can be built easily by iterating over the entire array and actually generating the chains while appending the index of their first element to the set. Once again, assume that A_{ind} is being updated to val. The cases that have to be handled for the update operation are as follows:

If val \bmod A_{ind-1} = 0 then delete any occurrence of ind from the set as the new value makes sure that it is a part of the chain that previously ended at ind-1.

If val \bmod A_{ind-1} â‰ 0 then add ind to the set as a new chain will have to start from ind.

If A_{ind+1} \bmod val = 0 then delete any occurrence of ind+1 from the set as A_{ind+1} will be part of the same set as A_{ind}.

If A_{ind+1} \bmod val â‰ 0 then add ind+1 to the set as a new chain will have to begin at ind+1.

### COMPLEXITY

O(Qlog(N) + Nlog(N))

### SOLUTIONS

Authorâ€™s Solution (Subtask 1)

Authorâ€™s Solution (100 points)

### TESTERâ€™S SOLUTION

Testerâ€™s Solution (Subtask 1)

Testerâ€™s Solution (100 points)