Алгоритмы сортировки

У Фермера Джона есть \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) ферм, пронумерованных от \(1\) до \(N\). Известно, что ФД закрывает ферму \(i\) в момент времени \(c_i\). Беси просыпается в момент времени \(S\) и хочет максимизировать производительность своего дня посетив как можно больше ферм, прежде чем они закроются. Она планирует посетить ферму \(i\) в момент времени \(t_i + S\). Беси должна прибыть на ферму строго раньше чем ФД закроет её, чтобы действительно посетить эту ферму.

У Беси есть \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\) запросов. Для каждого запроса она даёт Вам два целых числа \(S\) и \(V\). Для каждого запроса выведите сможет ли Беси посетить не менее \(V\) ферм, если она проснётся в момент времени \(S\).

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

• Если высоты двух соседних стогов сена различаются не более чем на \(K\) (\(1\le K\le 10^9\)), она может поменять местами два стога

Какую лексикографически минимальную последовательность высот Беси может получить после некоторой последовательности таких операций?

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

Имеется \(N\) (\(1 \le N \le 10^5\)) коров, которые потенциально могут посещать университет. Каждая корова готова платить за обучение максимум \(c_i\) (\(1 \le c_i \le 10^6\)). Фермер Джон может установить плату за обучение, которую все коровы должны оплатить. Если эта плата больше, чем корова готова платить, она не платит и не учится в университете. Фермер Джон хочет установить такую оплату, чтобы получить максимальную сумм оплат. Определите эту максимальную сумму и установленную плату за обучение.

В настоящий момент коровы выстроились в линию в порядке \(p_1, p_2, p_3, \dots, p_N\), и ФД стоит перед коровой \(p_1\). Он хочет переупорядочить коров так, чтобы они стали в порядке \(1, 2, 3, \dots, N\), с коровой \(1\) перед ФД.

Фермера Джона слышит только корова, которая стоит перед ним. В этот момент ФД может сказать ей перейти на \(k\) позиций назад (\(k\) в интервале \(1 \ldots N-1\).). \(k\) коров, которых она проходит, двигаются вперёд, освобождая место для неё, в которое она и становится.

Например, пусть \(N=4\) и коровы стоят в таком порядке

 ФД: 4, 3, 2, 1 

Единственная корова, которая слышит ФД, это корова \(4\). Если он скажет ей сдвинуться на 2 позиции, порядок станет таким:

 ФД: 3, 2, 4, 1 

Теперь ФД слышит только корова \(3\). Теперь ей можно давать инструкцию и т.д.

Определите последовательность инструкций (с минимальным их количеством), которые должен дать ФД, чтобы отсортировать всех коров.