🔴 Senior — массивы#

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

1. Кратчайший отрезок с заданной суммой#

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

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

Вывод: минимальная длина или 0, если решения нет.

Пример:

6 5
2 -1 2 3 -2 4

2

Требование: O(N) времени и O(N) дополнительной памяти. Обычное скользящее окно не работает при отрицательных числах. Используйте префиксные суммы и монотонную очередь индексов; суммы храните в 64-битном типе.

2. Количество инверсий#

Инверсией называется пара индексов i < j, для которой a[i] > a[j]. Найдите количество инверсий в массиве.

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

Вывод: число инверсий.

Пример:

5
2 3 8 6 1

5

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

3. Скользящая медиана#

Для каждого окна длины K выведите нижнюю медиану — элемент с индексом (K-1)/2 после сортировки окна по возрастанию.

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

Вывод: по одной нижней медиане для каждого окна.

Пример:

6 3
1 3 -1 -3 5 3

1 -1 -1 3

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

4. Долгоживущий буфер телеметрии#

Нужно хранить последовательность целых чисел и обработать Q команд:

• PUSH x — добавить x в конец;
• POP — удалить последний элемент; команда встречается только для непустой последовательности;
• GET i — вывести элемент с индексом i (индексация с нуля).

Общая верхняя граница числа команд известна, но будущая длина последовательности заранее неизвестна. Используйте std::vector, без ручного new[] и без копирования всего буфера при каждом добавлении.

Ввод: Q (1 ≤ Q ≤ 2·10^5), далее Q команд. Значения x удовлетворяют |x| ≤ 10^9; для GET гарантировано 0 ≤ i < size().

Вывод: ответы на команды GET в порядке обработки, затем элементы итоговой последовательности в одну строку. Для пустого результата выведите пустую строку.

Пример:

7
PUSH 4
PUSH 8
GET 0
POP
PUSH 6
GET 1
GET 0

4
6
4
4 6

Требование: суммарно O(Q) амортизированного времени и O(Q) памяти. Не вызывайте shrink_to_fit после каждого POP: это может вызвать лишние перемещения и не гарантирует точный размер буфера.