Production will stops iff exists integer K ≥ 0 such a·2K is divisible by m. From this fact follows that K maximum will be about O(log2(m)). So if we modeling some, for example, 20 days and production does not stop, then it will never stop and answer is "No". Otherwise answer is "Yes".
Let us find minimum length needed to cover points by Ox. It is Maximum(xi) - Minumum(xi). The same in Oy — Maximum(yi) - Minumum(yi). Since we need a square city to cover all the mines, then we need to set length of this square to the maximum from those two values.
Let us define function f(L, R), that gives answer to the query. It looks follows:
if L = R then f(L, R) = L;
else if 2b ≤ L, where b — maximum integer such 2b ≤ R, then f(L, R) = f(L - 2b, R - 2b) + 2b;
else if 2b + 1 - 1 ≤ R then f(L, R) = 2b + 1 - 1;
else f(L, R) = 2b - 1.
Total complexity is O(logR) per query.
Let us iterate over all different aj. Since we need to maximize , then iterate all integer x (such x divisible by aj) in range from 2aj to M, where M — doubled maximum value of the sequence. For each such x we need to find maximum ai, such ai < x. Limits for numbers allow to do this in time O(1) with an array. After that, update answer by value . Total time complexity is O(nlogn + MlogM).
Note, that d-sorting is just a permutation (call it P), because it does not depends on characters in string. Look at shuffling operation in different way: instead of going to the next substring and sort it, we will shift string to one character left. It remains to understand that shift of string the permutation too (call it C). Now its clear, we need to calculate S·P·C·P·C... = S·(P·C)n - k + 1. And after that shift string for k - 1 character to the left for making answer to the shuffling operation. Here we use the multiplication of permutations. Since they are associative, that we can use binary algorithm to calculate (P·C)n - k + 1. Total time complexity is O(nmlogn).
Let us note, that in optimal answer any segment that making a group contains their minimum and maximum values on borders. Otherwise it will be better to split this segment to two other segments. Another note that is every segment in optimal solution is strictly monotonic (increasing or decreasing). Paying attention to the interesting points in sequence which making local maximums (i. e. ai - 1 < ai > ai + 1), local minimums (ai - 1 > ai < ai + 1), and point adjacent to them. Solve the problem by dynamic programming: Di is the answer in the prefix i. To calculate Di we need to look at no more than three previous interesting points and to previous Di - 1. Total time complexity is O(n).
Let us note that we can use binary search to find answer to the one query. Suppose at some moment was fixed height h and need to know will fit the rectangle with width w and height h to the segment of fence from l-th to r-th panel. Let us build data structure that can answer to this question. This will be persistent segment tree with unusual function inside: maximum number of consecutive ones in segment (maxOnes). In leaves of segment tree will be only numbers 0 and 1. To calculate this function need to know some other values, specifically:
len — length of the segment in vertex of segment tree, prefOnes — length of prefix that consists only of ones, sufOnes — length of the suffix consist only of ones.
These functions are computed as follows:
maxOnes is equal to max(maxOnes(Left), maxOnes(Right), sufOnes(Left) + prefOnes(Right));
prefOnes equals prefOnes(Right) + len(Left) in case of len(Left) = prefOnes(Left), and prefOnes(Left) otherwise;
sufOnes equals sufOnes(Left) + len(Right) in case of len(Right) = sufOnes(Right), and sufOnes(Right) otherwise;
len = len(left) + len(Right);
Left и Right — it is left and right sons of vertex in segment tree.
As mentioned above, tree must be persistent, and it must be built as follows. First, builded empty tree of zeros. Next in position of highest plank need to put 1. The same doing for planks in decreasing order. For example if fence described with sequence [2, 5, 5, 1, 3] then bottom of segment tree will changed as follows:
[0, 0, 0, 0, 0] -> [0, 1, 0, 0, 0] -> [0, 1, 1, 0, 0] -> [0, 1, 1, 0, 1] -> [1, 1, 1, 0, 1] -> [1, 1, 1, 1, 1].
And we need to remember for all hi their version of tree. Now to answer the question we need to make query in our segment tree (that corresponding to height h) on segment [l, r]. If maxOnes form this query less than w, then rectangle impossible to put (otherwise possible).
Building of tree will take O(nlogn) time and memory. Time complexity to the one query will take O(log2n) time.