Заметим, что можно решать независимо по x и по y. Теперь у нас есть набор отрезков, надо для него найти лучшую точку. Не знаю, можно ли делать проще, я написал сканлайн. Можно за честно поддерживать сумму расстояний до ближайшей точки каждого отрезка в текущем x и на сколько меняется эта сумма при переходе к следующему x. Накидаем события вида "начало отрезка", "середина отрезка" и "конец отрезка", которые апдейтят изменение суммы на +-2. Ну и соберем минимум по всем x.

sqrt-декомпозиция. Преобразуем наши пары (x, y) в (x — y, y). Теперь при отрицательных значениях x надо прибавлять к ответу y, а иначе x + y. Рассмотрим блок длины корень по позициям в массиве [l, r]. Если элементы в нем посорчены по x, то для префикса отрицательных элементов надо взять сумму по y, а для суффикса остальных — сумму по x + y. Прекалкнем нужные префикс и суффикс суммы для блока. Также для блока будем лениво поддерживать число, которое надо прибавить ко всем его элементам. Находить префикс отрицательных можно бинпоиском. Получается что-то типа O(n sqrt(nlogn)), но заходит за 2 секунды, если нормально написать.

У меня в этой задаче какое-то сложное решение, возможно есть что-то проще.

С помощью динамики с битовыми масками за $$$O(2^t t^3)$$$ посчитаем cost[i][j] — минимальное время, чтобы начать с i-той типографии, облететь все остальные и закончить в j-той. Посчитаем также, сколько времени нужно, чтобы пролететь из магазина i в магазин j через все типографии, если для магазина i выбрано место i1, а для магазина j выбрано место j1. Сохраним эту информацию в массив $$$minD[i][j][i1][j1]$$$. Это можно сделать за $$$O(s^2 t^2)$$$, используя cost.

Подготовка закончена. Осталось запустить двоичный поиск по ответу. Чтобы проверить время T, будем сводить задачу к 2-SAT. Будет n переменных для каждого магазина, xi — истина, если мы хотим стоить магазин на 2 площадке. Найдём все магазины, что если мы построим выберем для i-того место i1, а для j-того место j1, то не успеем их облететь, т.е. $$$minD[i][j][i1][j1]>T$$$. Значит нужно или размещать i-тый магазин не на площадке i1, или размещать j-тый магазин не на площадке j1. Например, если $$$minD[2][3][0][1]>T$$$, то попросим или магазин x2 разместить на 2, или магазин x3 на 1, т.е. добавим (x2 or !x3). После этого, если 2-SAT скажет, что решение есть, то уменьшаем правую границу поиска, иначе увеличиваем левую.

Двоичным поиском подбираем ответ. Для проверки будем поддерживать самую правую границу, которую можем покрыть без дыр (изначально запишем как A). Проходим по всем отрезкам, отсортированным по левой границе. Если левая граница отрезка внутри покрытого диапазона, а правая расширяет диапазон, берём его. А в ответ можно вообще вывести все отрезки, которые пересекаются с [A,B] и стоят дешевле найденного значения.

Строим суффиксный массив. Для запроса находим все суффиксы, которые начинаются со строки s двоичным поиском. Они образуют некоторый отрезок [L,R), где L — первый индекс в суффиксном массиве суффикса, начало которого >= s, а R — первый индекс, для которого начало > s. Теперь нужно посчитать, сколько суффиксов начинаются в диапазоне [li, ri-|Mi|+1]. Для каждого запроса в его ответ добавим, сколько чисел в суффиксном массиве <=ri-|Mi|+1 попали в диапазон [L,R), и вычтем количество чисел <= li-1. Это можно сделать оффлайн с помощью дерева отрезков, или онлайн с помощью персистентного дерева отрезков.

Или динамикой или комбинаторикой можно решить эту задачу . Для динамики я не смог найти переходы ,там не так совсем гладко получается . Тяжело сделать так ,чтобы числа были в возрастающем порядке .

Посмотрим на отрезанные треугольники таким образом: трапеция и сверху треугольник. Тогда ответ можно считать, как сумма площадей всех треугольников минус сумма площадей трапеций. Площадь трапеции равна произведению высоты на полусумму оснований. Высоту мы знаем, она равна $$$y_i$$$. По подобию всего треугольника и отрезанной части понимаем, что основания равны $$$x$$$ и $$$x \cdot \frac{y_i}{h}$$$, где $$$x$$$ — это реальное основание треугольника, а $$$h$$$ — его реальная высота. Перепишем это в $$$\frac 1 2 \cdot y_i \cdot (x + \frac x h \cdot y_i)$$$ = $$$\frac 1 2 \cdot (y_i \cdot x + y_i^2 \cdot \frac x h)$$$.

Ну все, осталось аккуратно посмотреть, какие треугольники отрежутся прямой, а какие будут целиком под ней. Отсортируем треугольники по высоте, теперь можно искать ловербаундом. Посчитаем префикс-суммы площадей и суффикс-суммы $$$x$$$ и $$$\frac x h$$$. Из этого ответ находится тривиально.

Слово s похоже на слово t, если их посорченные по буквам копии совпадают. Закинем посорченные слова из словаря в сет, а дальше просто жадно посчитаем, сколько надо удалить. Обрабатываем слева направо, поддерживая, сколько подряд идущих плохих слов сейчас накопилось. Если это число больше $$$k$$$, то удалим слово, увеличим ответ и обнулим счетчик.

Перейдем от задачи "посчитать сумму на ромбе" к "посчитать сумму на прямоугольнике". Повернем плоскость на 45 градусов: каждая клетка (x, y) переходит в клетку (x + y, x — y). Ну а теперь это упражнение на 2D-фенвика.

Очевидно, что два числа, которые от нас просят, — это одна и та же задача, только решенная дважды с заменой всех open на close и наоборот. Будем решать только задачу на открытие.

Расстояние, которое необходимо пройти, зависит только от самого левого и самого правого закрытого гаража.

Тогда пусть у нас есть функция $$$check(l, r)$$$, которая умеет говорить, можно ли нажать рычаги так, чтобы все гаражи с $$$1$$$ по $$$l-1$$$ и с $$$r+1$$$ по $$$n$$$ были открыты, а гаражи с $$$l$$$ по $$$r$$$ находились в любом положении. Легко заметить, что при фиксированном $$$l$$$ данная функция монотонна по $$$r$$$. Поэтому можно написать два указателя вида: для $$$l$$$ найдем минимальное $$$r$$$, на которое $$$check$$$ возвращает true, обновим ответ расстоянием для них и увеличим $$$l$$$.

Это часть была тривиальна) Теперь о том, как написать такую функцию $$$check$$$. Посмотрим на рычаг, который мы нажмем последним. Он откроет некоторые гаражи, которые нам нужны, и обязательно не закроет ни один из нужных. Дальше взглянем на предпоследний: он тоже откроет некоторые нужные, но этот может закрыть некоторые гаражи, которые откроет последний. Таким образом, можно понять, что можно всегда нажимать на такой рычаг, у которого все закрываемые гаражи будут открыты позднее (буду их называть свободными). Пишется это проще всего, видимо, так. Поддерживаем булев массив, который говорит, свободен ли гараж. Поддерживаем для каждого рычага количество несвободных гаражей, которые он закрывает. Будем поддерживать очередь из рычагов, которые еще на нажаты, но у которых это значение равно нулю. Когда мы выставляем некоторый гараж свободным, он обновляет это значение у всех рычагов, которые его закрывают, и добавляет рычаги, у которых значение стало равно нулю, в очередь. Выставим гаражи с $$$l$$$ по $$$r$$$ свободными, а дальше очередь сама все доделает. Когда мы достаем очередной рычаг из очереди и нажимаем его, то он выставляет некоторым гаражам статус свободных. Если после того, как очередь стала пустой, все нужные гаражи свободны, то результат — true.

Научимся считать $$$dist(i, j)$$$ — расстояние, которое суммарно пройдут $$$i$$$-й синий человек и $$$j$$$-й красный человек до ближайшей точки встречи. Если отрезок между ними не пересекает ни одного круга, то это просто евклидово расстояние. Иначе можно показать, что оба из них должны идти по касательной к какому-либо кругу (возможно, к различным). Построим для обоих все 4 касательные, переберем касательную первого, касательную второго, и проверим, что отрезки от них до точки пересечения касательных не пересекает окружности. Найдем минимальное из валидных расстояний.

Ну а когда у нас есть такая функция, осталось всего лишь найти совершенное паросочетание минимального веса на этом двудольном графе, где в левой доле синие люди, а в правой — красные. Можно сделать венгерским алгоритмом.

Заметим, что для некоторого $$$k$$$ существует всего $$$\frac n k$$$ запрещенных позиций. То есть суммарно для всех $$$k$$$ от $$$2$$$ до $$$n$$$ их $$$n \log n$$$. Как этим пользоваться? Посортим позиции в массиве по значению в них по невозрастанию. Тогда можно идти в этом порядке и искать первую разрешенную позицию. Для любого $$$k$$$ придется просмотреть не более $$$\frac n k$$$ позиций, пока не найдем разрешенную.

Действительно, дп по цифрам. Число хорошее, если в любом отрезке длины $$$k$$$ в нем все цифры различны. Посчитаем заранее до всех тесткейзов $$$ok[N][K]$$$ — является ли число $$$N$$$ ($$$N < 10^4$$$) хорошим при $$$k=K$$$.

Стандартно перейдем к $$$ans = calc(r) - calc(l - 1)$$$. $$$calc(x)$$$ посчитаем с помощью $$$dp[idx][last][last~len][less]$$$: набрали $$$idx$$$ цифр, $$$last$$$ — число, образованное последними $$$\le k$$$ цифрами, $$$last~len$$$ — его длина (до $$$k$$$, соответственно), а $$$less$$$ — флаг, который говорит, совпадает ли префикс числа $$$x$$$ с набранным префиксом длины $$$idx$$$. Переберем следующую цифру: если префикс совпадает, то от $$$0$$$ до $$$x[idx]$$$, иначе до $$$9$$$. Приписываем цифру к $$$last$$$ и переходим, если $$$ok[new number][min(k, last~len + 1)]$$$.

В задаче просят посчитать количество перестановок длины $$$n$$$ таких, что длины всех циклов кратны $$$k$$$. Рассмотрим, какую динаму нам надо написать. Пусть $$$dp_i$$$ будет количеством способов поставить $$$i$$$ чисел в перестановку, но с одним условием. В каждом переходе в такой динамике мы выбираем набор позиций, замыкаем все выбранные позиции в цикл, НО одна из этих позиций обязательно первая из свободных на данный момент. Это нам позволяет считать каждую перестановку по одному разу. То есть каждый переход из $$$dp_i$$$ выглядит так: переберем $$$d$$$ — делитель $$$k$$$, зафиксируем набор позиций (с учетом того, что первая позиция берется однозначно) $$$C(i - 1, d - 1)$$$, домножим на количество способов замкнуть $$$d$$$ позиций в цикл ($$$(d-1)!$$$ — известный факт, наверняка легко доказать) и прибавим к $$$dp_{i+d}$$$. Ну и $$$dp_n$$$ тогда будет ответом.

Проблема, однако, в том, что не очень понятно, как считать $$$C(n, k)$$$ по непростому модулю. Посмотрим пристальнее — у нас есть выражение вида $$$C(n, k) \cdot k! = A(n, k)$$$. Распишем дальше $$$A(n, k) = \frac{1 \cdot 2 \cdot \dots \cdot n}{1 \cdot 2 \cdot \dots \cdot (n-k)} = (n-k+1) \cdot (n-k+2) \cdot \dots \cdot n$$$. Теперь это просто произведение последовательных чисел, и никакого деления не нужно для их вычисления. Тогда можно просто построить ДО над всеми числами от $$$1$$$ до $$$n$$$ и запрашивать в нем произведение на отрезке.

На самом деле, в задаче можно сдать и $$$n^2$$$) Заметим, что нам в динаме нужны только столбцы $$$C(n, k)$$$ для делителей $$$k$$$ минус один) Будем просто подсчитывать $$$C(n, k)$$$, как обычно считаем за квадрат, и сохраним только эти столбцы. У меня зашло за 0.8c из 2.

Честного решения не знаю, но можно запихать тернарник по углу.

Заметим, что минимум/максимум на прямоугольнике — это всегда минимум/максимум в $$$a$$$, умноженный на минимум/максимум в $$$b$$$ (там немного надо посмотреть на то, какие знаки получатся при произведении). Тогда будем поддерживать ДО с операциями прибавить на отрезке и найти пары (минимум, количество минимумов) и (максимум, количество максимумов). Ну все, теперь мы оставили не более $$$2$$$ чисел в отрезке из $$$a$$$ и не более $$$2$$$ чисел в отрезке из $$$b$$$, а ответ не изменился. Переберем их попарные произведения и найдем минимум и максимум.

Есть один случай, когда минимум или максимум равны нулю. Тогда количество минимумов/максимумов — это количество пар произведений, в которых хотя бы одно число равно нулю. Тоже легко считается с той информацией, которую мы оставили от отрезков.