🟠 Middle — массивы#

Четыре авторские задачи. Следите за временем выполнения и дополнительной памятью: лишние копии крупных массивов могут привести к превышению лимита.

1. Слияние лент#

Даны два массива кодов посылок, каждый отсортирован по неубыванию. Слейте их в один отсортированный массив. Если одинаковый код есть в обоих массивах, сохраните оба экземпляра.

Ввод: размеры N и M (0 ≤ N,M ≤ 2·10^5, N+M ≥ 1), затем N чисел и M чисел (|a_i| ≤ 10^9).

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

Пример:

4 3
1 4 4 9
2 4 10

1 2 4 4 4 9 10

Требование: O(N+M) времени. Сначала реализуйте слияние в новый вектор; затем оцените память и объясните, почему запись результата прямо во входные массивы здесь не предполагается.

2. Длинный спокойный отрезок#

Дан ряд измерений. Найдите длину самого длинного непрерывного отрезка, в котором разность максимального и минимального значения не превышает K.

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

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

Пример:

8 3
1 3 6 7 4 5 2 3

Пояснение: отрезок 7 4 5 2 имеет длину 4, минимум 2 и максимум 7, поэтому он не подходит; подходит, например, 4 5 2 3, его размах равен 3.

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

3. Частые значения на отрезках#

Дан массив целых оценок и Q запросов. Для каждого запроса [L,R] выведите сумму элементов этого отрезка. Индексы запросов в условии нумеруются с единицы.

Ввод: N (1 ≤ N ≤ 2·10^5), массив из N чисел (|a_i| ≤ 10^9), число запросов Q (1 ≤ Q ≤ 2·10^5), затем Q пар L R (1 ≤ L ≤ R ≤ N).

Вывод: ответ на каждый запрос в отдельной строке.

Пример:

8
10
4

Требование: подготовка O(N), каждый запрос O(1), всего O(N+Q) времени. Используйте long long; хранить отдельный массив для каждого запроса нельзя.

4. Циклический буфер измерений#

Реализуйте буфер фиксированной вместимости C. Изначально он пуст. Команда A x добавляет значение в конец, если буфер заполнен — удаляет самый старый элемент перед добавлением. Команда Q выводит элементы от самого старого к самому новому. После каждой команды A ничего не печатайте.

Ввод: C и Q (1 ≤ C ≤ 2·10^5, 1 ≤ Q ≤ 2·10^5), затем Q команд: A x (|x| ≤ 10^9) или P.

Вывод: для каждой команды P выведите размер буфера и его элементы от старого к новому. Если команд P нет, вывода нет.

Пример:

3 6
A 5
A 8
A 2
P
A 9
P

3 5 8 2
3 8 2 9

Требование: добавление O(1), память O(C). Не сдвигайте элементы при удалении самого старого; используйте кольцевую индексацию. Не храните всю историю команд вместо самого буфера.