Задачу можно решать разными способами, но я попоробую рассказать самое короткое решение, которое только смог придумать.

Найдем bounding box закрашенных клеточек. Пускай мы будем знать его левую границу l, правую границу r, верхнюю границу u и нижнюю границу d. Теперь заметим, что у нас может быть только два случая:

1. Левая верхняя клетка одного квадрата находится в (u, l), правая нижняя клетка другого квадрата находится в (d, r).

2. Левая нижняя клетка одного квадрата находится в (d, l), правая верхняя клетка другого квадрата находится в (u, r).

Рассмотрим первый случай. Мы уже знаем, что первый квадрат находится в (u, l). Осталось найти, где находится второй квадрат. Для этого переберем размер k квадратов. Теперь осталось заметить, что нам достаточно проверять, закрашены ли клетки на границах bounding box'a (не все, а лишь те, что находятся на расстоянии k от уголков), чтобы определить, не взяли ли мы слишком большое k. Теперь мы с легкостью можем восстановить позицию второго квадрата: (d - k + 1, r - k + 1).

Второй случай аналогичен первому.

Сложность решения: O(n²).

Какие планки нам выгодно красить в первую очередь? А какие в последнюю?

Подсчитаем, какое количество планок нам нужно для i-го цвета. Теперь заметим, что закрашенные в нужный цвет планки мы уже никогда не сможем перекрасить. Поэтому будем красить жадно, стараясь «правильно» закрашивать как можно меньшее количество планок. Для этого отсортируем цвета по частоте во входных данных. Ну а дальше проходим и за линейное время считаем ответ.

Сложность решения: .

Возможно, с упорядоченными данными проще работать...

Попробуем зафиксировать какое-то число. Пусть это будет i. Есть числа меньшие, чем i, а есть...

Попробуем разбить все числа на группы размера i. Возможно, в таких группах будет проще подсчитывать сумму остатков.

Моя любимая задача на этом туре. Реализация — короткая, а идея — суперская.

Воспользуемся сортировкой подсчетом. Ответ будем считать как , где , a cnt_i — количество чисел равных i. Осталось эффективно подсчитывать sum_i.

Заметим, что все числа меньшие i дают в качестве остатка свое собственное значение, поэтому нам достаточно подсчитать сумму всех чисел, меньших i. С большими числами поступим похитрее. Разобьем их на такие отрезки: [i, 2·i), [2·i, 3·i), [3·i, 4·i), ... Научимся быстро находить ответ для таких отрезков.

Раcсмотрим отрезок [k·i, (k + 1)·i). Заметим, что число k·i + j при делении на i дает остаток j. Поэтому, если мы просто прибавим к ответу число k·i + j, то ответ будет увеличен на k·i больше, чем нужно. Поэтому, если мы сложим все числа из отрезка [k·i, (k + 1)·i), то нам нужно будет убрать (k·i)·cnt_{k·i..(k + 1)·i}. Поэтому сумму остатков на таком промежутке можно вычислить как sum_{k·i..(k + 1)·i} - (k·i)·cnt_{k·i..(k + 1)·i}.

Такое решение требует O(n) времени на сортировку и на вычисление ответа.

Количество начальных вершин совпадает с количеством путей, да? Вместо того, чтобы сортировать строки, попробуйте отсортировать вершины. А зная k-ю начальную вершину можно и сам путь найти.

Если склеить два ребра длинны 1, то получится одно ребро длины 2. А если два длинны 2, то получится одно длины 4...

Ничего страшного не произойдет, если мы случайно решим задачу для более длинных маршрутов.

Что-то я разленился. Если в кратце, то задача аналогична построению суффиксного массива. Что забавно, но можно написать решение, которое практически не зависит от m. Давайте будем считать m = 2²⁰, что даже больше, чем может быть во входных данных. Удлинять ребра в два раза будем точно так же как и в методе двоичного подъема.

Сложность по времени: .

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

Сложность по времени: O(n²).

Будем хранить счетчик вложенности. А можно еще хитрее. Если встретили открывающую скобку, то уменьшаем k, если закрывающую — увеличиваем. В таком случае, если мы встретили единичку, то к ответу прибавляем 4^k = 2^2·k. Таким образом, задачу можно решить в один проход.

Сложность по времени: O(n).

Обратите внимание на то, что числа отличаются не больше, чем на 1.

Если для i j таких, что i ≤ j, выполняется условие a_i ≤ a_j, то можно утверждать, что ответ не менее a_j - a_i + 1

Предположим, что мы посчитали ответ для двух соседних отрезков. Что нам нужно знать, чтобы быстро посчитать ответ для объединенного отрезка?

Научимся объединять соседние отрезки. Пусть мы знаем ответ для отрезка [l, m) и отрезка [m, r). Попробуем получить ответ для отрезка [l, r). Тут всего три простых случая:

1. Максимальный ответ находится в левом отрезке;
2. Максимальный ответ находится в правом отрезке;
3. Максимальный ответ пересекает границу m.

Для первых двух случаев ответ очевиден, а для третьего ответ находится так:

max{a_m, a_m + 1, ..., a_r - 1} - min{a_l, a_l + 1, ..., a_m - 1} + 1

Чтобы быстро отвечать на запросы построим дерево отрезков, которое будет хранить минимум, максимум и ответ на отрезке. Таким образом, мы сможет отвечать на каждый запрос за время .

Сложность по времени: .

Попробуйте решить для маленьких тестов. Нет, не ручками, а с помощью динамического программирования.