реализация

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

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

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

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

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

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

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

Амбар описан простым (несамопересекающимся прямоугольником) с вершинами в целочисленных координатах \((x_1, y_1) \ldots (x_n, y_n)\) перечисленных по часовой стрелке. Его рёбра чередуются между горизонтальными (параллельными оси Х и вертикальными - параллельными оси Y). Первое ребро может быть как вертикальным, так и горизонтальным. Выход расположен в точке \((x_1, y_1)\). Беси начинает внутри амбара, в одной из некоторых вершин \((x_i, y_i)\) для \(i > 1\). Она может двигаться только по периметру амбара, по часовой стрелке либо против часовой стрелки. Её цель - пройти минимальное расстояние до выхода. Это относительно легко, когда свет включён. Поскольку она просто должна выбрать какой путь короче от текущего положения до выхода - по часовой стрелке или против часовой стрелки.

Когда свет выключается, Беси паникует и забывает вершину, в которой она находится. К счастью, она всё ещё помнит точную карту амбара, поэтому она может вычислить свою позицию, двигаясь по периметру и используя свои ощущения. Когда она стоит в вершине (включая свою начальную вершину), она может ощутить внутренний угол при этой вершине. и также она может сказать является ли эта вершина выходом. Когда она движется вдоль амбара, она может определить точную длину ребра, по которому прошла. Беси двигается в соответствии со следующей стратегией: она движется по часовой стрелке по периметру амбара, до тех пор, пока она не ощутит достаточное количество углов и рёбер, чтобы определить, в какой вершине она сейчас находится. В этой точке она легко может вычислить, как ей быстрее добраться до выхода - продолжив движение по часовой стрелке или переключившись на движение против часовой стрелки.

Помогите Беси определить наибольшую величину, на которую возрастёт её путь к выходу в темноте, по сравнению с путём при свете (рассмотрев все возможные положения стартовой вершины).

Давайте назовём два города "специальной парой", если они удовлетворяют этому свойству и принадлежат разным штатам. Коровам интересно сколько всего существует "специальных пар". Помогите им!

Вам даны целые числа \(M\) и \(K\) \((1 \leq M \leq 10 ^ 9, 1 \leq K \leq 31)\). Выберите положительное целое \(N\) и сконструируйте последовательность \(a\) из \(N\) неотрицательных целых чисел так, чтобы выполнялись следующие условия:

• \(1 \le N \le 100\)
• \(a_1 + a_2 + \dots + a_N = M\)
• \(\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K\)

Если такой последовательности не существует, выведите \(-1\).

\(\dagger \text{ popcount}(x)\) это количество \(1\) в двоичном представлении числа \(x\). Например, popcount от \(11\) это \(3\), а popcount от \(16\) это \(1\).

\(\dagger \oplus\) это оператор побитового XOR.

Ввод содержит \(T\) (\(1 \le T \le 5 \cdot 10^3\)) независимых подтестов.

У Беси есть простой неориентированный граф с вершинами, помеченными \(1\dots N\) (\(2\le N\le 750\)). Она генерирует поиск в глубину графа вызывая функцию \(\texttt{dfs}(1)\), описанную следующим C++ кодом. Каждый список соседних вершин (\(\texttt{adj}[i]\) для всех \(1\le i\le N\)) может быть переставлен произвольно перед началом поиска в глубину, поэтому граф может иметь множество возможных DFS-порядков.

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // adjacency list
vector<int> dfs_order;

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    dfs_order.push_back(x);
    for (int y : adj[x]) dfs(y);
}

Вам дано начальное состояние графа, а также стоимость изменения состояния каждого ребра. А именно, для каждой пары вершин \((i,j)\) удовлетворяющей \(1\le i<j\le N\), Вам дано целое число \(a_{i,j}\) (\(0<|a_{i,j}|\le 1000\)) такое, что

• Если \(a_{i,j}>0\), ребро \((i,j)\) сейчас отсутствует в графе, оно может быть добавлено за стоимость \(a_{i,j}\).
• Если \(a_{i,j}<0\), ребро \((i,j)\) сейчас в графе, оно может быть удалено за стоимость \(-a_{i,j}\).

Определите минимальную суммарную стоимость изменить граф так, чтобы \([1,2\dots,N]\) стало возможным DFS-обходом.

**Замечание: мы не рекомендуем использовать для решения этой задачи язык программирования Питон, чтобы получить полный балл по этой задаче. **

\(N\) (\(1 \leq N \leq 7500\)) коров Фермера Джона стоят в ряд. Корова \(1\) стоит в начале этого ряда, а корова \(N\) - в конце. \(i\)-ая корова имеет разновидность \(a_i\) (\(1 \leq a_i \leq N\)).

ФД везет своих коров на осмотр в местную больницу для крупного рогатого скота. Однако ветеринар, специализирующийся на коровах, очень придирчив и хочет провести осмотр \(i\)-ой коровы в очереди, только если она относится к виду \(b_i\) (\(1 \leq b_i \leq N\)).

ФД ленивый и не хочет полностью переупорядочивать его коров. Он выполняет следующую операцию ровно один раз.

• Выбирает два числа \(l\) и \(r\) такие, что \(1 \leq l \le r \leq N\). Реверсирует порядок коров между \(l\)-ой и \(r\)-ой коровами включительно.

ФД хочет измерить насколько эффективен его подход. Для каждого \(c=0 \ldots N\), помогите ФД помогите ФД определить количество различных операций (\(l,r\)) таких, что ровно \(c\) коров будут проверены ветеринаром. Две операции (\(l_1,r_1\)) и (\(l_2,r_2\)) считаются различными, если \(l_1 \neq l_2\) или \(r_1 \neq r_2\).

Беси помогает Эльзе играть со словами. Слова берутся из банка, содержащего \(M\) различных слов, ни одно слово не является префиксом другого.

Пока банк не пустой, Беси выбирает слово из банка, удаляет его из банка, читает его Эльзе по одному символу за раз слева направо. Задача Эльзы сказать Беси, как только она уникально определит слово, после чего Беси прекращает чтение.

Беси уже решила читать слова из словаря в порядке \(w_1,w_2,\dots,w_M\). Если Эльза ответит так быстро, как это возможно, сколько символов из каждого слова прочитает Беси?

Слова заданы в сжатом формате. Сначала мы определяем \(N+1\) (\(1\le N\le 10^6\)) различных слов и затем банк слов состоит из всех этих слов, ни одно из которых не является префиксом другого. Слова определяются следующим образом:

• Изначально, 0-ое слово - пустая строка.
• Затем для каждого each \(1\le i\le N\), \(i\)-ое слово будет равно \(p_i\)-ому слову плюс дополнительный символ в конце (\(0\le p_i<i\)). Символы выбираются так, что все \(N+1\) слов различны.

**Замечание: Время на тест для этой задачи 3сек, в 1.5 большее чем по умолчанию. Память на тест для этой задачи 512MB, в два раза больше чем по умолчанию.**

Беси проходит тест вида да/нет из \(N\) вопросов (\(1\le N\le 2\cdot 10^5\)). За \(i\)-ый вопрос она может добавить \(a_i\) баллов если ответит правильно, и отнять \(b_i\) баллов, если ответит неправильно или не изменить сумму, если не ответит вообще на вопрос (\(0<a_i,b_i\le 10^9\)).

Беси знает ответы на все вопросы, но боится, что администратор теста Эльза подменит до \(k\) вопросов так, чтоб получилось, что Беси ответила неправильно.

Заданы \(Q\) (\(1\le Q\le N+1\)) кандидатов величин \(k\) (\(0\le k\le N\)), определите количество баллов, которые Беси гарантированы для каждого \(k\), зная, что она должна ответить не менее чем на \(k\) вопросов.

У Фермера Джона есть булевское выражение длиной в \(N\) слов (\(1 \leq N < 2 \cdot 10^5\), \(N\) нечётное). Только \(\texttt{true}\) or \(\texttt{false}\) появляются на нечётных позициях, и только \(\texttt{and}\) и \(\texttt{or}\) появляются на чётных позициях.

Фраза вида \(x\text{ OPERATOR }y\), где \(x\) и \(y\) или \(\texttt{true}\) или \(\texttt{false}\), а \(\text{OPERATOR}\) есть \(\texttt{and}\) или \(\texttt{or}\), вычисляется следующим образом:

• \(x\texttt{ and }y\): Это вычисляется в true если оба \(x\) и \(y\) true, иначе в false.
• \(x\texttt{ or }y\): Это вычисляется в true если или \(x\) или \(y\) true, иначе в false.

При вычислении выражения ФД действует так: Аналогично C++, \(\texttt{and}\) имеет более высокий приоритет чем \(\texttt{or}\). Более подробно: для вычисления выражения повторяется следующий шаг пока в выражении не останется ровно одно слово.

1. Если выражение содержит \(\texttt{and}\), выбирается любой из них и фраза, окружающая его, заменяется её вычислением.
2. Иначе, выражение содержит \(\texttt{or}\). Выбирается любой из них и фраза, окружающая его, заменяется её вычислением.

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

У ФД есть \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\) запросов. В каждом запросе она даёт Вам два целых числа \(l\) и \(r\) (\(1 \leq l \leq r \leq N\), \(l\) и \(r\) оба нечётные), и удаляет сегмент от ключевого слова \(l\) до ключевого слова \(r\) включительно. Он хочет заменить удалённый сегмент одним \(\texttt{true}\) или \(\texttt{false}\) так, чтобы оставшееся выражение вычислялось к определённому булевскому значению. Помогите ФД определить, возможно ли это.

У Фермера Джона есть перестановка \(p\) длины \(N\) (\(2 \leq N \leq 10^5)\), содержащая каждое положительное целое от \(1\) до \(N\) ровно один раз. Однако Фермер Нхой прокрался в амбар ФД и испортил \(p\). Чтобы не быть совсем плохим, ФН написал несколько советов, которые помогут ФД восстановить \(p\). Пока в \(p\) было более одного элемента, ФН делал следующее:

Пусть оставшиеся элементы \(p\) есть \(p'_1, p'_2, \dots , p'_n\),

• Если \(p'_1 > p'_n\), он записывал \(p'_2\) и удалял \(p'_1\) из перестановки.
• Иначе, он выписывал \(p'_{n-1}\) и удалял \(p'_n\) из перестановки.

В конце у ФН получились выписанные \(N - 1\) целых чисел \(h_1, h_2, \dots, h_{N-1}\), в указанном порядке. По заданным числам \(h\) ФД просит у Вас помощи реконструировать лексикографически минимальную перестановку \(p\), соответствующую алгоритму ФН или определить, что ФН сделал ошибку. Напомним, что если Вам даны две перестановки \(p\) и \(p'\), то \(p\) лексикографически меньше чем \(p'\), если \(p_i < p'_i\) в первой позиции, \(i\), где они различаются.

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

У Фермера Джона есть \(N\) коров (\(2 \le N \le 10^5\)) пронумерованных от \(1\) до \(N\). Каждая корова любит ровно один тип сена \(h_i\) (\(1 \le h_i \le N\)). ФД хочет, чтобы все его коровы любили один тип сена.

Чтобы это случилось, ФД может сформировать фокус-группы. Фокус-группа состоит из всех коров в непрерывном интервале от \(i\) до \(j\), включительно. Если в фокус-группе более половины коров любит один и тот же некоторый тип сена, то все коровы начинают любить этот тип сена, иначе ни у одной коровы не изменяется любимый тип сена. Например, если фокус группа состоит из 16 коров, 9 или более из которых любят один и тот же тип сена, то и остальные 7 коров теперь будут любить этот же тип сена.

ФД хочет узнать, какие типы сена могут стать любимыми всем коровами. В один момент времени он может создать только одну фокус группу, но он может последовательно создавать сколько угодно фокус-групп, чтобы все коровы полюбили один и тот же тип сена.

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность \(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за минуту ( \(0 \leq a_i \leq 10^8\)).

Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке. От него требуется отцеплять их по одной, отправляя прочь для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова (скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой максимально возможное количество молока, которое может собрать фермер Джон, если он отцепляет своих коров в оптимальном порядке.

Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что каждый запрос рассматривает временное потенциальное изменение независимо от всех других запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.

**Примечание. Ограничение по времени для этой задачи составляет 4 секунды, что в два раза больше, чем по умолчанию. Ограничение по памяти для этой задачи составляет 512 МБ, вдвое больше, чем по умолчанию.**

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строка "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiebessie».

Дана строка \(s\), пусть \(B(s)\) представляет собой максимальное количество повторяющихся копий. из «bessie» можно получить, удалив ноль или более символов из \(s\). В приведенном выше примере \(B(\)"bqessiyexbesszieb"\() = 2\). Кроме того, учитывая строка \(t\), пусть \(A(t)\) представляет собой сумму \(B(s)\) по всем непрерывным подстроки \(s\) строки \(t\).

У фермера Джона есть строка \(t\) длины не более \(2\cdot 10^5\), состоящая только из символов a-z. Пожалуйста, рассчитайте \(A(t)\) и как \(A(t)\) изменится после \(U\) (\(1\le U\le 2\cdot 10^5\)) обновлений, каждое из которых изменяет символ \(t\). Обновления являются кумулятивными.

**Замечание: Время на тест в этой задаче 4s, в два раза больше чем по умолчанию. Ограничение по памяти для этой задачи 512MB, в два раза больше чем по умолчанию.**

У Фермера Джона \(N\) (\(2\le N\le 2\cdot 10^5\)) тракторов, где -ый трактор может использоваться только в интервале \([l_i,r_i]\) включительно. Интервалы для тракторов имеют левые конечные точки \(\ell_1<\ell_2<\dots<\ell_N\) и правые конечные точки \(r_1<r_2<\dots<r_N\). Некоторые из тракторов специальные.

Два трактора \(i\) и \(j\) называются соседними если \([\ell_i,r_i]\) и \([\ell_j,r_j]\) пересекаются. ФД может перебраться (выполнить трансфер) с одного трактора на любой соседний трактор. Путь между двумя тракторами \(a\) и \(b\) состоит трансферов таких, что первый трактор в последовательности есть \(a\), последний трактор в последовательности есть \(b\) и каждые два трактора в последовательности соседние. Гарантируется ,что имеется путь из трактора \(1\) в трактор \(N\). Длина пути - количество трансферов (или эквивалентно, количество тракторов минус один).

Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый указывает пару тракторов \(a\) и \(b\) (\(1\le a<b\le N\)). Для каждого запроса выведите два целых числа:

• Длину любого кратчайшего пути между тракторами \(a\) и \(b\).
• Количество специальных тракторов, таких, что существует как минимум один кратчайший путь из трактора \(a\) в трактор \(b\), содержащий его.

Очень жаркое лето. Фермер Дон решил купить некоторое количество кондиционеров.

У ФД имеется \(N\) коров (\(1 \leq N \leq 20\)), которые живут в амбаре, содержащем последовательность стойл, пронумерованные \(1 \ldots 100\). Корова \(i\) занимает диапазон стойл, начиная с \(s_i\) и заканчивая в \(t_i\). Диапазоны стойл, занимаемые коровами, не пересекаются. У коров различные требования к охлаждению. Корова \(i\) должна быть охлаждена на количество \(c_i\). Это значает, что для всех стойл, занимаемых коровой \(i\) температура должна быть уменьшена на \(c_i\) единиц.

Амбар содержит \(M\) кондиционеров, помеченных \(1 \ldots M\) (\(1 \leq M \leq 10\)). \(i\)-ый кондиционер стоит \(m_i\) единиц денег, если работает и охлаждает воздух (уменьшает температуру) в стойлах начиная в \(a_i\) и заканчивая в \(b_i\). Если работает, \(i\)-ый кондиционер уменьшает температуру во всех стойлах этого диапазона на величину \(p_i\) (\(1 \leq p_i \leq 10^6\)). Диапазоны стойл кондиционеров могут перекрываться.

Определите минимальное количество денег, которое ФД должен потратить, чтобы сделать температуру комфортабельной для всех коров во всех стойлах. Гарантируется, что это возможно сделать.

Беси собирается в путешествие по Cowland, которая имеет \(N\) (\(2\le N\le 2\cdot 10^5\)) городов, пронумерованных от \(1\) до \(N\) и \(M\) (\(1\le M\le 4\cdot 10^5\)) односторонних дорог. \(i\)-ая дорога ведёт из города \(a_i\) в город \(b_i\) и имеет метку \(l_i\) (\(1\le a_i,b_i\le N\), \(1\le l_i\le 10^9\)).

Путешествие длины \(k\) начинается в городе \(x_0\) - это последовательность городов \(x_0, x_1, \ldots, x_k\), таких, что что существует дорога из города \(x_i\) в город \(x_{i+1}\) для всех \(0\le i < k\). Гарантируется, что не существует путешествий бесконечной длины, и что никакие две дороги не соединяют одну и ту же пару городов.

Для каждого города Беси хочет узнать наидлиннейшее путешествие, начинающееся в этом городе. Для некоторых стартовых городов может существовать несколько наидлиннейших путешествий - из них Беси предпочитает путешествие с лексикографически минимальной последовательностью меток дорог. Последовательность лексикографически меньше другой последовательности такой же длины, если на первой позиции, где они различаются, первая последовательность имеет меньший элемент, чем вторая последовательность.

Выведите длину и сумму меток дорог, предпочитаемого Беси путешествия, начинающегося из каждого города.

Коровы Фермера Джона любят конфетные трости. У ФД \(N\) коров с определённой начальной высотой. Он хочет скормить им \(M\) конфетных тростей, различной высоты (\(1\le N,M\le 2\cdot 10^5\)).

ФД планирует кормить коров конфетными тростями одну за одной в порядке, в котором они заданы на вводе. Чтобы кормить коров ФД вывешивает конфетные трости так, чтобы изначально они касались земли. Коровы выстраиваются одна за одной в порядке, как они заданы на входе. Каждая ест до своей высоты (потому что выше не достаёт). Трость остаётся на месте где она изначально была подвешена и не опускается к земле, даже после того как её нижняя часть съедена. Возможно, что когда подойдёт очередь некоторой коровы она ничего не сможет съест, если нижняя часть трости уже выше высоты этой коровы. После того как пройдёт очередь всех коров, они подрастают на высоту равную количеству единиц трости, которую съела корова, а ФД вывешивает новую конфетную трость и коровы повторяют процесс опять (корова 1 всегда начинает есть первой).

Каждая вершина \(i\) в этом дереве ассоциируется с породой, имеющей целое число пятен \(s_i\). Дисбалансом такого дерева называется максимум \(|s_i-s_j|\) по всем парам \((i,j)\) таким, что \(j\) есть предок \(i\).

Фермер Джон не знает точное значение \(s_i\) для каждой породы, но он знает нижнюю и верхнюю границу этих величин. Ваша задача - назначить значения \(s_i \in [l_i,r_i]\) (\(0\le l_i\le r_i\le 10^9\)) каждой вершине так, чтобы минимизировать дисбаланс этого дерева.