## Editorial for An Animal Contest 1 P4 - Alpaca Arrays

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: WilliamWu277

For each query, we can iterate through all the values of and such that in time. For each pair of and , we loop through indices to of the array to check whether both and are present within that range. If so, we can print YES.

Time Complexity:

We store the queries in an array and sort them by their value for offline processing. Set an array where stores the most recent appearance of the number . Initially we set all these values to , then for each query, we can update the index of the most recent appearance of all numbers which appear before or at the index . To answer each query we iterate through all the values of and such that in time. For each pair , we check whether both and are less than or not. If not, the answer to that query would be YES. Then, we just need to make sure that the answers are outputted in the correct order. This can be done by giving each query an based on the order in which it is read from input.

Time Complexity:

Alternatively, there is another solution that does not require offline processing. Store the indices of the appearances of each number in separate lists. For each query, we can iterate through all the values of and such that in time. In the lists storing the appearances of each divisor, we binary search for the index that would take if it were in the array and similarly for . If the value of these two indices are the same, this means that there are no occurrences of that specific number between and . For both divisors, if the results from the previous step are not the same, we print YES.

Time Complexity: