A. Very Important Persons

There are two main ways to solve the problem.

The first way is to assign guests to seats by diagonals, starting from the seat (1, 1). You should be careful with considering cases n < m and m < n when implementing traversal.

The second way is a more common solution which however requires more advanced algorithm. Let us run BFS from (1, 1) and assign seats to guests in order they are popped from the queue, starting from the most important one.

B. Least Common Multiple

Let p / q be divisible by both a / b and c / d, all fractions are irreducible. So the numbers (p / q): (a / b) = (p·b) / (q·a) and (p / q): (c / d) = (p·d) / (q·c) are integers.

Since p·b is divisible by q·a, b and a are relatively prime, then p is divisible by a. p and q are also relatively prime, so b is divisible by q. Similar argument allows to conclude that p is divisible by с, and d is divisible by q.

Therefore p is divisible by lcm(a, c), q is a divisor of gcd(b, d). The fraction lcm(a, c) / gcd(b, d) is divisible by both a / b and c / d, and is therefore the smallest such fraction. So the answer is lcm(a, c) / gcd(b, d).

C. Bad Order

You have to add numbers to the given array to convert it to a permutation that requires maximal number of swaps when being sorted by selection sort.

First suppose that the permutation is fixed. Let us find the number of swaps that selection sort makes. Consider permutation as a set of cycles. Let us consider a cycle that contains the minimal number that occupies wrong position. Length of this cycle is greater than 1. After we make a swap, it is split to two cycles: of length 1, and 1 shorter than its initial length. Therefore the cycle of length L will be split L - 1 times, so the number of swaps required is n - c, where c is the number of cycles.

Therefore we must add numbers to the given array in such way that the number of cycles in the resulting permutation was minimal possible. To do it consider the given array as a directed graph, if a[i] = j, add an edge from i to j. The graph is a union of cycles and paths. All cycles in the graph will remain there after we convert the array to a permutation. All paths can be concatenated to a single long cycle (vertices without both incoming and outgoing edges are considered paths of length 0). To do so, order paths arbitrarily, and add an edge from the end of each path to the beginning of the next path. Finally make them a single cycle by adding an edge from the end of the last path to the beginning of the first one.

D. Red-Black Tree

First you must notice a subtle hint in the first sentence of the statement. It is easy to prove (or find in any data structures textbook) that red-black tree with n vertices has O(log(n)) black vertices on any path from the root to a leaf. Let us use this fact in our solution.

Let us call a tree almost red-black if its coloring satisfies all constraints of the red-black tree, except that its root is red.

We can now use dynamic programming to calculate for each subtree the number of ways to color it to become red-black or almost red-black, and to have the number of black vertices on any path from its root to a leaf equal to h.

Let us denote the described number of ways as d[v][h][t], here v is the vertex, h is the number of black vertices on any path from v to a leaf in its subtree, t is the type of coloring, t equal to 0 would, for example, mean that the subtree is red-black, and t equal 1 would mean that the subtree is almost red-black.

Now d[v][h][0] is the product for all u children of v of values (d[u][h - 1][0] + d[u][h - 1][1]). Similarly, d[v][h][1] is the product for all u children of v of values d[u][h][0].

The answer to the problem is the sum for all h of values d[1][h][0].

Since h for all valid colorings is limited by C = O(log(n)), we can consider the number of colorings be zero if h > C.

So we only need O(nlog(n)) states, and O(1) to calculate the result for each state. The time complexity is O(nlog(n)).

E. Array Study

Since there are the same constrains to n and q, let us use n instead of max(n, q). Let us make some observations.

Observation one: the answer to the query is the maximal length of [L, R], such that pref_L - 1 = pref_R, where pref_i = a₁ + a₂ + ... + a_i is the prefix sum of the given array. Let us move from the initial array to the array of prefix sums and for a query [l, r] look for the longest subarray of [l - 1, r] such that pref_L = pref_R.

Observation two: pref_i are quite small ( - n ≤ pref_i ≤ n).

Let us make use of queries given offline. Our method will be similar to Mo's algorithm. Split all queries to groups, the i-th group will contain queries [l_i, r_i] such that i·K ≤ l_i < (i + 1)·K (here K is approximately sqrt(n)). In each group sort queries by their right end. Let us solve the problem separately for each group.

Consider the i-th group, where l_i is in [L_i, R_i]. Let us consider queries by non-decreasing of r_i, and maintain two arrays: mostLeft[p] and mostRight[p] — the first after R_i and the last before r occurrence of the prefix sum p. Using these two values, we can find the answer that is subarray of [R_i + 1, r]. To get the complete answer to [l, r] query, let us calculate the answer with the beginning of the required subarray at [l, min(r, R_i)] using mostRight array, and take maximum of that value and the optimal subarray for [R + 1, r].

So it takes O(K·c_i + n) to answer all queries of one group, here c_i is the number of queries in that group. Adding up all O(n / K) groups, we get the total time complexity O(sum(i = 1... n / K: K·c_i + n)) = O(K·sum(c_i) + n² / K). Setting K = sqrt(n) we get O(n·sqrt(n)) complexity.