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], такого, что prefL - 1 = prefR, где prefi = a1 + a2 + ... + ai — префиксная сумма массива a (pref0 = 0). Далее будем считать, что мы работаем с массивом pref0, pref1, ..., prefn, и по запросу [l, r] требуется найти максимальный по длине подотрезок [L, R] отрезка [l - 1, r], такой, что prefL = prefR.
Второе наблюдение: prefi — довольно маленькие ( - n ≤ prefi ≤ n).
Будем решать задачу оффлайн. Воспользуемся методом, во многом похожим на алгоритм Мо. Разобьем все запросы на группы, где в i-й группе содержатся запросы [li, ri], такие, что i·K ≤ li < (i + 1)·K (K — константа, приблизительно равная sqrt(n)). В каждой группе отсортируем запросы по правой границе. Теперь решим задачу отдельно для каждой группы запросов.
Рассмотрим i-ю группу [Li, Ri]. Будем идти подряд по запросам слева направо (то есть по неубыванию правой границы). Также будем поддерживать два массива mostLeft[p] и mostRight[p] — текущее самое левое вхождение префиксной суммы p, которое также левее Ri и текущее самое правое вхождение префиксной суммы p. Поддерживая эти два массива, также несложно поддерживать ответ на отрезке [Ri + 1, r], где r — правая граница текущего запроса. Для ответа на запрос [l, r] посчитаем за O(K) ответ на [l, min(r, R)], используя информацию из массива mostRight и сравним это значение с текущим ответом на отрезке [R + 1, r].
Итого, на запросы каждый группы в сумме мы тратим O(K·ci + n) времени, где ci — количество запросов в группе. Так как групп всего O(n / K), получаем суммарное время работы O(sumi = 1... n / K(K·ci + n)) = O(K·sum(ci) + n2 / K). При K = sqrt(n) получаем время работы O(n·sqrt(n))
