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

**Примечание. Ограничение по времени для этой задачи – 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\) возвращается к исходному значению перед следующим запросом.

Фермер Джон развозит сено по ферме.

Ферма имеет \(N\) \((1\le N\le 2\cdot 10^5)\) амбаров, расположенных в целых точках \(x_1,\dots, x_N\) \((0 \le x_i \le 10^6)\) на числовой прямой. ФД запланировал \(N\) перевозок сена в некоторую целую точку \(y\) \((0 \le y \le 10^6)\) и затем одну перевозку к каждому амбару.

К несчастью служба доставки очень расточительна. В частности, для некоторых \(a_i\) и \(b_i\) \((1\le a_i, b_i\le 10^6)\), \(a_i\) пакетов сена теряются на единицу расстояния каждой доставки влево и \(b_i\) пакетов сена теряются на единицу расстояния каждой доставки вправо. Формально при транспортировке из точки \(y\) в амбар в точке \(x\), количество теряемых пакетов сена определяется как

Вам даны \(Q\) \((1\le Q\le 2\cdot 10^5)\) независимых запросов, каждый состоит из возможных значений \((a_i,b_i)\), помогите ФД определить наименьшее количество потерянных пакетов сена, если он выберет \(y\) оптимально.

Коровы передают две строки \(s\) и \(t\), каждая с длиной не более \(10^5\), состоящие только из маленьких латинских букв от 'a' до 'r'. Вы должны ответить на \(Q\) запросов (\(1 \leq Q \leq 10^5\)). Для каждого запроса нужно ответить, совпадут ли строки, если в каждой из них оставить только указанные в запросе маленькие латинские буквы (удалив все остальные символы).

К несчастью, возможна ситуация противоречивости ответов всех коров. Это означает, что не все коровы говорили правду. Вычислите минимальное количество коров, которые солгали.

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\) (\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний на всех занятиях не превышает \(10^{18}\).

Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз на каждом занятии.

Единственный способ Эльзы модифицировать свои записи - объединить два соседних занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\) тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\) Если Эльза выберет разделить третье занятие на два, то лог может стать одним из \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).

По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

Чтобы играть в эту игру, Беси выбирает некоторый интервал, например \(i\)-ый. И Эльза выбирает некоторый интервал, например, \(j\)-ый, возможно тот же самый. Для заданной величины \(k\) они выигрывают, если \(a_i + a_j \leq k \leq b_i + b_j\).

Для всех \(k\) в интервале \(0 \ldots 2M\), посчитайте количество упорядоченных пар \((i,j)\) для которых Беси и Эльза выиграют в эту игру.

Как подающий надежды фотограф, Беси решила сделать несколько фото этих цветков. В частности, для каждой пары цветков \((i,j)\) где \(1\le i\le j\le N\), Беси делает фото всех цветков от \(i\) до \(j\) (включая \(i\) и \(j\)).

Затем Беси посмотрела на эти фотки и заметила, что некоторые фото имеют "средний цветок" - цветок, который имеет \(P\) лепестков, где \(P\) - точное среднее число лепестков среди всех цветков на этом фото.

Сколько из фотографий Беси имеют "средний цветок"?

Фермер Джон остановился около игры и хочет узнать минимальное количество обменов между соседними элементами, которые нужно совершить, чтобы игра получила ничейный счёт. ФОРМАТ ВВОДА (файл balance.in): Первая строка ввода содержит \(N\), следующая строка содержит \(2N\) целых чисел каждое из которых равно 0 или 1. ФОРМАТ ВЫВОДА (файл balance.out): Выведите количество соседних обменов, которые нужно сделать, чтобы игра получила ничейный счёт.

Ферма Джона построена вдоль прямой дороги, поэтому любое место фермы может быть описано позицией на этой дороге (точка на числовой прямой). ФД построил \(N\) рогаток (\(1 \leq N \leq 10^5\)), \(i\)-ая из которых описывается тремя целыми числами \(x_i\), \(y_i\), \(t_i\), указывающими, что рогатка может переместить навоз из позиции \(x_i\) в позицию \(y_i\) за \(t_i\) единиц времени.

У ФД есть \(M\) лотков с навозом для транспортировки (\(1 \leq M \leq 10^5\)). \(j\)-ый лоток нужно переместить из позиции \(a_j\) в позицию \(b_j\). Перемещение лотка с навозом на тракторе на расстояние \(d\) занимает \(d\) единиц времени. ФД надеется сократить время использованием рогаток. Время перемещения трактора без навоза не учитывается.

Для каждого из \(M\) лотков определите минимально возможное время транспортировки. при условии использования не более одной рогатки.

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

Выведите значения всех \(K\) при которых Вы можете заработать максимальную оценку по этой схеме оценивания, в отсортированном порядке.

Еда будет представлять собой непрерывный интервал, содержащий один или более последовательных стогов сена (нельзя менять их порядок). Общий вкус еды равен сумме вкусов на интервале. Общая пряность еды - максимум из пряностей на интервале.

ФД хочет определить минимальную пряность, кторую можно достичь, чтобы вкус был не менее \(M\) (\(1 \le M \le 10^{18}\)).