A. Очень важные гости

Есть два способа решить эту задачу.

Первый заключается в том, чтобы рассаживать гостей по диагоналям, начиная от позиции (1, 1). Требуется некоторая аккуратность в реализации, чтобы верно учесть случаи n < m и m < n.

Второй способ позволяет не задумываться о том, в какую сторону вытянут прямоугольник. Просто запустим обход в ширину от места (1, 1), и будем рассаживать гостей, начиная от максимального номера, в порядке извлечения мест из очереди.

B. Наименьшее общее кратное

Пусть p / q нацело делится на a / b и c / d, при этом все дроби несократимые. Тогда целыми числами являются (p / q): (a / b) = (p·b) / (q·a) и (p / q): (c / d) = (p·d) / (q·c).

p·b делится на q·a. Поскольку b и a взаимно просты, p делится на a. p и q тоже взаимно просты, поэтому b делится на q. Аналогично, p делится на с и d делится на q.

Таким образом, p делится lcm(a, c), q делит gcd(b, d). Дробь lcm(a, c) / gcd(b, d) является наименьшей подходящей дробью, и она делится на a / b и c / d. Таким образом, ответ равен lcm(a, c) / gcd(b, d).

C. Портим порядок

В задаче требуется дополнить исходный массив до перестановки чисел от 1 до n таким образом, чтобы сортировка выбором сделала наибольшее число обменов.

Для начала допустим, что мы уже сгенерировали какую-то перестановку и хотим узнать, сколько обменов совершит сортировка выбором. Для этого будем рассматривать перестановку как набор циклов. Рассмотрим цикл, в котором содержится минимальное число, которое стоит не на своём месте. Длина этого цикла больше чем 1. Нетрудно заметить, что при одном обмене длина соответствующего цикла уменьшается на один и появляется новый цикл длины 1. Теперь заметим, что цикл длины L уменьшит свою длину ровно L - 1 раз в процессе сортировки, из чего следует, что суммарно длины циклов уменьшатся ровно на n - c, где c — количество циклов.

Таким образом нам нужно дополнить массив до перестановки таким образом, чтобы количество циклов получилось минимальным. Для этого рассмотрим перестановку как ориентированный граф, где если a[i] = j, то в графе есть ребро из вершины i в вершину j. Граф разбился на циклы и цепочки. Все циклы, которые есть в этом графе, сохранятся и после добавления недостающих элементов, а все имеющиеся цепочки (вершину, не имеющую ни входящих, ни исходящих ребер, будем считать цепочкой длины 0) можно объединить в один большой цикл. Пройдемся по всем имеющимся цепочкам и будем добавлять ребро из конца одной цепочки в начало другой. Когда все цепочки соединены в одну, добавим ребро из её конца в начало, и она станет циклом.

D. Красно-черное дерево

Заметив тонкий намек в первом предложении условия, легко доказать (или проверить в любой книге по структурам данных), что в любом красно-черном дереве с n вершинами, на пути от корня до листьев O(logn) черных вершин. Воспользуемся этим фактом в решении.

Назовем почти красно-черным дерево, в котором выполняются все свойства красно-черного дерева, но корень дерева покрашен в красный цвет.

С помощью динамического программирования посчитаем для каждого поддерева количество способов покрасить вершины в нем так, чтобы поддерево было красно-черным, и количество черных вершин на пути от корня до листьев равнялось h, или чтобы дерево было почти красно-черным, и количество черных вершин на пути от корня до листьев равнялось h.

Сохраним это количество способов в массиве d[v][h][t], где v — номер вершины, являющейся корнем поддерева, h — количество черных вершин на пути от корня до листьев, а t обозначает тип покраски, при t равном 0, там хранится количество покрасок, чтобы поддерево стало красно-черным, а при t равном 1, чтобы поддерево стало почти красно-черным.

Тогда d[v][h][0] равняется произведению по всем u, являющимся детьми v, значений (d[u][h - 1][0] + d[u][h - 1][1]). А d[v][h][1] равняется произведению по всем u, являющимся детьми v, значений d[u][h][0].

Ответ на задачу будет равен сумме по всем d[1][h][0].

Теперь заметим, что h для всех допустимых раскрасок поддеревьев ограничено некоторой величиной C = O(log(n)), и при всех h > C, количество покрасок гарантированно будет равняться нулю.

Значит, необходимо всего O(nlog(n)) состояний, из каждого из которых идет O(1) переходов. Следовательно решение будет работать за O(nlog(n)).

E. Изучение массива

Поскольку ограничения на n и q совпадают, будем использовать в n вместо max(n, q). Сделаем несколько наблюдений.

Первое наблюдение: ответ на запрос — максимальная длина отрезка [L, R], такого, что pref_L - 1 = pref_R, где pref_i = a₁ + a₂ + ... + a_i — префиксная сумма массива a (pref₀ = 0). Далее будем считать, что мы работаем с массивом pref₀, pref₁, ..., pref_n, и по запросу [l, r] требуется найти максимальный по длине подотрезок [L, R] отрезка [l - 1, r], такой, что pref_L = pref_R.

Второе наблюдение: pref_i — довольно маленькие ( - n ≤ pref_i ≤ n).

Будем решать задачу оффлайн. Воспользуемся методом, во многом похожим на алгоритм Мо. Разобьем все запросы на группы, где в i-й группе содержатся запросы [l_i, r_i], такие, что i·K ≤ l_i < (i + 1)·K (K — константа, приблизительно равная sqrt(n)). В каждой группе отсортируем запросы по правой границе. Теперь решим задачу отдельно для каждой группы запросов.

Рассмотрим i-ю группу [L_i, R_i]. Будем идти подряд по запросам слева направо (то есть по неубыванию правой границы). Также будем поддерживать два массива mostLeft[p] и mostRight[p] — текущее самое левое вхождение префиксной суммы p, которое также левее R_i и текущее самое правое вхождение префиксной суммы p. Поддерживая эти два массива, также несложно поддерживать ответ на отрезке [R_i + 1, r], где r — правая граница текущего запроса. Для ответа на запрос [l, r] посчитаем за O(K) ответ на [l, min(r, R)], используя информацию из массива mostRight и сравним это значение с текущим ответом на отрезке [R + 1, r].

Итого, на запросы каждый группы в сумме мы тратим O(K·c_i + n) времени, где c_i — количество запросов в группе. Так как групп всего O(n / K), получаем суммарное время работы O(sum_{i = 1... n / K}(K·c_i + n)) = O(K·sum(c_i) + n² / K). При K = sqrt(n) получаем время работы O(n·sqrt(n))