🟡 Middle — массивы#

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

1. Объединение двух поставок#

Даны два массива, отсортированных по неубыванию: A длины N и B длины M. В A уже выделено место для N + M чисел: первые N ячеек содержат данные, оставшиеся M предназначены для результата. Объедините массивы в A, сохранив сортировку. Дополнительный массив создавать нельзя.

Ввод: N M (0 ≤ N,M ≤ 2·10^5), затем N чисел массива A и M чисел массива B (|x| ≤ 10^9).

Вывод: объединённый отсортированный массив длины N + M.

Пример:

4 3
1 4 7 9
2 4 10

1 2 4 4 7 9 10

Требование: O(N+M) времени и O(1) дополнительной памяти. Заполняйте A с конца, чтобы не перезаписать необработанные значения.

2. Самый длинный бюджетный отрезок#

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

Ввод: N S (1 ≤ N ≤ 2·10^5, 0 ≤ S ≤ 10^18), затем N чисел cost_i (0 ≤ cost_i ≤ 10^9).

Вывод: максимальная длина подходящего отрезка.

Пример:

6 8
2 1 3 2 4 1

3

Требование: O(N) времени и O(1) дополнительной памяти. Используйте скользящее окно: неотрицательность цен гарантирует, что при сдвиге левой границы сумма не увеличится. Для суммы используйте 64-битный тип.

3. Максимум в каждом окне#

Для каждого непрерывного окна длины K выведите максимальное значение массива.

Ввод: N K (1 ≤ K ≤ N ≤ 2·10^5), затем N целых чисел a_i (|a_i| ≤ 10^9).

Вывод: N-K+1 максимумов в порядке окон.

Пример:

8 3
1 3 -1 -3 5 3 6 7

3 3 5 5 6 7

Требование: O(N) времени и O(K) дополнительной памяти. Используйте двустороннюю очередь индексов: удаляйте устаревшие индексы слева и меньшие значения справа. Не копируйте каждое окно.

4. Циклический сдвиг части массива#

Дан массив и полуинтервал [L, R) — элементы с индексами L, L+1, ..., R-1. Циклически сдвиньте только этот участок вправо на K позиций. Остальная часть массива не меняется. K может быть больше длины участка.

Ввод: N L R K (1 ≤ N ≤ 2·10^5, 0 ≤ L < R ≤ N, 0 ≤ K ≤ 10^18), затем N целых чисел.

Вывод: массив после сдвига.

Пример:

7 1 6 2
10 20 30 40 50 60 70

10 50 60 20 30 40 70

Требование: O(N) времени и O(1) дополнительной памяти. Сведите K по модулю длины участка и используйте три разворота подотрезков.