Для начала отсечем случай, когда n нечетно. Так как периметр прямоугольника всегда четный, то ответ в таком случае 0.
Если n четно, то количество прямоугольников, которые можно составить, равно n / 4. Если n кратно 4, то мы посчитаем и квадрат, который составлять нельзя, поэтому в таком случае из ответа нужно вычесть единицу.
Асимптотика решения — O(1).
Для начала найдем минимум в заданном массиве, обозначим его переменной minimum. Понятно, что всегда возможно покрасить n * minimum клеток. Тогда понятно, что нужно найти такой минимум в массиве, перед которым слева стоит как можно больше чисел, больших чем минимум. Другими словами, нужно найти два минимума, расстояние между которыми наибольшее, с учетом цикличности. Если же минимум в массиве один, то понятно, что начинать красить нужно с цвета, который находится сразу после него (опять же с учетом цикличности). Это можно сделать за один проход по массиву, поддерживая в отдельной переменной позицию ближайшего слева минимума. Если текущее число равно минимуму, тогда нужно обновить эту переменную и ответ.
Асимптотика решения — O(n), где n — количество различных цветов.
Давайте строить ответ рекурсивно. При k = 0 в качестве ответа можно взять либо - 1 или + 1. Пусть теперь мы строим ответ для некоторого k > 0. Сначала построим ответ для k - 1 теперь как ответ для k возьмем четыре копии ответа для k - 1, инвертировав все значения в последней копии. Получается на самом деле некоторый фрактал с базой размера 2 × 2: 00, 01. Корректность доказать достаточно просто, если оба вектора из верхней (нижней) половины их левые половины дают скалярное произведение равное 0 и правые тоже дают 0. Если же один из векторов из верхней половины, а другой из нижней, то значение в левой половине будет противоположно значению в правой, поэтому сумма будет равна 0.
Можно заметить, что на самом деле ответом также является матрица в которой клетка i, j равна \texttt{+}, если количество битов в числе i|j четно.
Асимптотическая сложность: O((2k)2).
Давайте сначала объединим все отрезки, находящиеся в одной горизонтали или вертикали. Теперь ответ на задачу есть сумма длин всех отрезков минус количество пересечений. Посчитаем количество пересечений. Для этого будем идти горизонтальной сканирующей прямой снизу вверх (это можно делать событиями открылся вертикальный отрезок, закрылся вертикальный и обработать горизонтальный) и в некоторой структуре данных поддерживать множество x-координат открытых отрезков. В качестве структуры данных можно использовать дерево Фенвика с предварительным сжатием координат. Теперь для текущего горизонтального отрезка нужно просто взять количество открытых вертикальных отрезков со значениями x в отрезке x1, x2, где x — вертикаль на которой находится вертикальный отрезок, а x1, x2 — x-координаты концов текущего горизонтального отрезка.
Асимптотическая сложность: O(nlogn).
Рассмотрим медленное решение этой задачи: на первый запрос будем просто переприсваивать символы, на запросы второго типа будем идти по строке s и поддерживать указатель на текущую позицию в перестановке алфавита. Будем двигать указатель по циклу пока не найдем совпадение с текущим символом в s. После этого подвинем указатель еще раз. Тогда ответом на задачу будет количество циклических переходов (от последнего к первому символу) в перестановке алфавита. На самом деле это значение равно единице плюс количество пар соседних символов таких, что второй символ находится не правее первого. Таким образом, ответ на задачу зависит лишь от значений cntij —- количество пар соседних символов таких, что первый символ ест i, а второй j. Теперь, чтобы ускорить решение будем поддерживать дерево отрезков в вершине, которого находится матрица cnt для текущего подотрезка и символы с левого и правого концов текущего отрезка. Чтобы слить двух сыновей в дереве отрезков нужно просто попарно сложить значения матриц в левом и правом сыне, и обновить значением правого символа левого отрезка с левым символов правого отрезка.
Асимптотическая сложность: O(nk2 + mk2logn).
