Линейные структуры

Фермер Джон растит \(N\) пород коров (\(1 \leq N \leq 100,000\)), каждое из его полей предназначено для пастбища одной специфической породы коров, например, поле предназначенное для коров породы 12 может быть использовано только для коров породы 12 и не может быть использовано для коров других пород. Длинная дорога идёт вдоль фермы. Имеется последовательность из \(N\) полей вдоль одной стороны дороги (по одному для каждого типа коров) и \(N\) полей вдоль другой стороны дороги (тоже по одному для каждого типа коров). Когда корова пересекает дорогу, она переходит из одного поля, предназначенного для этой породы коров в другое поле, предназначенное для этой породы коров.

Если бы ФД "подумал вперёд" он мог бы упорядочить поля под породы таким образом, чтобы поля для одной и той же породы по разные стороны дороги находились друг напротив друга, и никакие коровы не могли бы столкнуться при переходе дороги. Однако упорядочивание полей по породам с разных сторон дороги может быть и различным, и тогда могут быть пары пород, для которых их пути пересекаются при переходе дороги. Пара различных пород \((a,b)\) называется "пересекающейся", если любой путь через дорогу для коровы породы \(a\) должен пересекаться с любым путём через дорогу для коровы породы \(b\).

ФД хочет минимизировать количетво пересекающихся пар пород. По логистическим причинам ФД может перемещать коров "по кругу" на одной стороне дороги, так что поля осуществляют "циклический сдвиг". То есть для некоторого \(0 \leq k < N\), каждая корова перемещается на \(k\) полей вперёд, а коровы из последних \(k\) полей пермещаются в первые \(k\) полей. Например, если поля на одной стороне дороги упорядочены так: 3, 7, 1, 2, 5, 4, 6 и выполняется сдвиг на \(k=2\), то новый порядок будет такой: 4, 6, 3, 7, 1, 2, 5. Определите минимальное возможное количество пересекающихся пар пород, которые могут существовать после соответствующего циклического сдвига полей на одной стороне дороги.

Как известно, коровы - существа привычки, поэтому они переходят дорогу одним и тем же способом каждый день. Каждая корова приходит в поле в точке, отличающейся от той, в которой она с него уходит, и все эти точки для разных коров также отличаются друг от друга. У ФД есть \(N\) коров, последовательно пронумерованных \(1 \ldots N\), Поэтому имеется ровно \(2N\) точек у дороги. ФД выписал все эти точки по номерам коров, по часовой стрелке, сформировав последовательность из \(2N\) чисел, каждое из которых встречается в этой последовательности ровно дважды. Он не записывал, является ли эта точка точкой входа или точкой выхода.

По его карте точек ФД хочет узнать, сколько путей различных пар коров могут пересечься в течение дня. Он называет пару коров \((a,b)\) пересекающейся парой, если путь коровы \(a\) от входа к выходу должен пересечься с путём коровы \(b\) от входа к выходу. Помогите ФД вычислить общее количество пересекающихся пар.

У ФД есть ровно \(n\) коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, \(c_i\) коров стоит перед дверью с номером \(i\). Разумеется, \(\сумма c_i = n\).

Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через \(d\) дверей отнимает у неё \(d^2\) энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров, теперь им есть что почитать. К несчастью, последний номер содержит довольно неподходящую статью, как приготовить совершенный бифштекс. ФД хочет чтобы его коровы не увидели эту статью.

ФД взял текст из журнала и создал строку S длиной не более чем 10^6 символов. Из неё он хочет удалить все вхождения подстроки T длиной <= 100 символов неподходящего содержания. Чтобы сделать это, ФД ищет первое вхождение T в S и удаляет его. Затем он повторяет процесс опять, снова удаляя первое вхождение T, продолжая так до тех пор, пока больше не станет вхождений T в S. Заметим, что удаление одного вхождения может создать другое вхождение, которое не существовало раньше.

Пожалуйста, помогите ФД определить конечное содержание строки S после завершения всех удалений.

Формат входных данных

Первая строка содержит S. Вторая строка будет содержать T. Длина T не более чем длина S, и все символы S и T - маленькие латинские буквы (a..z).

Формат выходных данных

Строка S после завершения всех удалений. Гарантируется, что S не станет пустой после завершения процесса всех удалений.

Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом переключившись на другой не более одного раза за все игры. Например, она может играть "Копыто" первые \(x\) игр, и затем переключится на "бумагу" на оставшиеся \(N-x\) игр.

По заданной последовательности жестов ФД, определите максимальное количество игр, которое выиграет Бесси.

Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать \(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\)) пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время \(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\) немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени \(T\).

Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая максимально возможное значение величины \(T\). Ваша задача - определить минимально возможное подходящее значение \(K\).

Помогите ФД определить размер наибольшей группы коров, которую он сможет сфотографировать.

Сумма может не поместится в 32-битное целое, Вы можете использовать 64-битное целое ("long long" в C/C++).

Она уже выбрала место - кусок земли \(N\) метров по \(M\) метров (\(1 \leq N, M \leq 200\)). К несчастью, на этом месте есть болотистые участки, на которых строительство невозможно. Помогите Беси определить наибольшую (по площади) область, на которой можно построить форт, так , чтобы форт не проходил через болотистые участки.

У Фермера Джона есть массив \(a\) из \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) неотрицательных целых чисел и целое число \(M\) (\(1 \leq M \leq 10^9\)). Затем ФД спрашивает у Беси число \(x\). За одну операцию ФД может выбрать индекс \(i\) и вычесть или прибавить \(1\) к \(a_i\). ФД называет число скучным - если оно равно минимальному количеству операций, которые он должен выполнить, чтобы \(a_i-x\) стало делится на \(M\) для всех \(1 \leq i \leq N\).

Среди всех возможных \(x\) выберите минимально возможное скучное число.

Фермер Джон хочет справедливо разделить пакеты сена между его двумя любимыми коровами Беси и Эльза. У него есть \(N\) ( \(1\le N\le 2\cdot 10^5\)) пакетов сена, упорядоченных в невозрастающем порядке. Где \(i\)-ый пакет сена имеет \(a_i\) единиц сена ($2\cdot 10^5\ge a₁\ge a₂ \ge \dots \ge a_N \ge 1$).

ФД хочет разделить непрерывный отрезок пакетов \(a_l, \dots, a_r\) между Беси и Эльзой, рассматривая пакеты в порядке от \(l\) до \(r\), и когда рассматривает \(i\)-ый пакет он даёт его корове, у которой сейчас меньше сена. Если равно - даёт Беси.

Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый описывается тремя целыми числами \(l,r,x\) (\(1\le l\le r\le N\), \(|x|\le 10^9\)). Для каждого запроса, введите на сколько больше единиц сена будет у Беси, после обработки пакетов от \(l\) до \(r\), если Беси начнёт с количеством сена на \(x\) единиц больше чем у Эльзы. Заметим эта величина отрицательна, если вначале у Эльзы будет на \(x\) единиц больше чем у Беси.

Беси посадила траву на положительной вещественной прямой. У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы. И она посадит траву \(i\)-го сорта на интервале \([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).

Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\) (\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\) перекрываются на длину не менее \(k_i\).

SCORING:

• Тесты 4-5: \(N \leq 5000\)
• Тесты 6-11: \(k\) одинаковое для всех интервалов
• Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).