1. Идея

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

• добавлять элементы;
• удалять одно вхождение элемента;
• быстро узнавать минимум;
• быстро узнавать максимум.

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

Для такой задачи удобно хранить все элементы в структуре данных, которая:

• поддерживает повторяющиеся значения;
• хранит элементы в отсортированном виде;
• позволяет быстро брать первый и последний элемент.

В C++ для этого идеально подходит multiset.

В Python в эталонном решении используется другой, но тоже стандартный подход:

• словарь counts хранит количество каждого значения;
• куча min_heap помогает находить минимум;
• куча max_heap помогает находить максимум.

2. Наблюдения

Наблюдение 1. Нужны повторы

Если просто использовать set, то одинаковые значения сольются в одно, а это неверно.

Например, после запросов:

• 1 5
• 1 5
• 2 5

в наборе должен остаться один 5.

Поэтому в C++ нужен именно multiset.

Наблюдение 2. Минимум и максимум должны находиться быстро

Если каждый раз искать минимум и максимум полным перебором, получится слишком медленно: до 2 * 10^5 запросов.

Нужна структура, где:

• вставка работает быстро;
• удаление работает быстро;
• минимум и максимум берутся быстро.

Наблюдение 3. В Python нельзя удалить произвольный элемент из кучи быстро

В Python стандартная heapq умеет хорошо:

• добавлять элемент;
• брать минимум.

Но она не умеет быстро удалять произвольное значение из середины кучи.

Поэтому используется приём с "ленивым удалением":

• реальное количество каждого числа хранится в counts;
• в кучах могут лежать уже удалённые значения;
• перед ответом на запрос мы выкидываем из вершины кучи все числа, которых уже нет в counts.

3. Алгоритм

Решение на C++17

Поддерживаем multiset<long long> s.

Обработка запросов:

• 1 x
  добавляем x в s через s.insert(x).

• 2 x
  находим одно вхождение x через s.find(x) и удаляем именно этот итератор: s.erase(it).

• 3
  минимум — это первый элемент: *s.begin().

• 4
  максимум — это последний элемент. Для этого берём s.end(), сдвигаемся на один назад и выводим значение.

Решение на Python 3

Поддерживаем:

• counts — словарь значение -> сколько раз оно есть сейчас;
• min_heap — куча для минимума;
• max_heap — куча для максимума, в неё кладём -x, чтобы стандартная min-heap работала как max-heap.

Обработка запросов:

• 1 x

  • увеличиваем counts[x];
  • кладём x в min_heap;
  • кладём -x в max_heap.

• 2 x

  • уменьшаем counts[x];
  • если количество стало нулём, удаляем ключ из словаря.

• 3

  • пока вершина min_heap уже не существует в counts, удаляем её;
  • после очистки вершина и есть текущий минимум.

• 4

  • пока число -max_heap[0] уже не существует в counts, удаляем его из кучи;
  • после очистки вершина даёт текущий максимум.

4. Почему это работает

C++17

multiset хранит все элементы в отсортированном порядке и разрешает дубликаты.

Тогда:

• после вставки элемент просто оказывается на своём месте;
• при удалении через find удаляется ровно одно вхождение;
• первый элемент в отсортированном контейнере — это минимум;
• последний элемент — это максимум.

Значит все запросы обрабатываются корректно.

Python 3

Здесь важно понять, почему работают две кучи и словарь.

Что хранится в counts

counts[x] — это настоящее количество числа x в наборе в текущий момент.

Именно словарь определяет, какие элементы действительно существуют.

Что хранится в кучах

В кучах лежат все когда-либо добавленные элементы, даже если некоторые из них уже были удалены позже.

То есть в куче могут оставаться "мёртвые" значения.

Почему ленивое удаление корректно

Когда нужно вывести минимум:

• смотрим на вершину min_heap;
• если этого числа уже нет в counts, значит оно удалено из набора и не должно участвовать в ответе;
• удаляем его из кучи;
• повторяем, пока на вершине не окажется реально существующее число.

После этого вершина кучи — наименьшее из всех существующих чисел, потому что:

• куча всегда отдаёт минимальный из лежащих в ней элементов;
• все несуществующие элементы с вершины мы убрали;
• значит первый оставшийся существующий элемент и есть настоящий минимум.

Точно так же работает и максимум через max_heap.

5. Сложность

C++17

Каждый запрос работает за O(log n):

• вставка в multiset — O(log n);
• удаление одного элемента — O(log n);
• получение минимума и максимума — O(1) на вывод значения по итератору.

Итоговая сложность: O(n log n).

Память: O(n).

Python 3

• добавление в кучи: O(log n);
• изменение словаря: O(1) в среднем;
• удаление из набора: O(1) в среднем по словарю;
• очистка кучи происходит лениво.

Хотя в одном конкретном запросе можно удалить несколько устаревших элементов из кучи, каждый такой элемент удаляется из кучи не больше одного раза за всё время работы. Поэтому суммарно все такие удаления дают O(n log n).

Итоговая сложность: O(n log n).

Память: O(n).

6. Код на C++17

#include <iostream>
#include <set>

using namespace std;

int main() {
    int n;
    cin >> n;

    multiset<long long> s;

    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;

        if (type == 1) {
            long long x;
            cin >> x;
            s.insert(x);
        } else if (type == 2) {
            long long x;
            cin >> x;
            auto it = s.find(x);
            s.erase(it);
        } else if (type == 3) {
            cout << *s.begin() << '\n';
        } else if (type == 4) {
            auto it = s.end();
            --it;
            cout << *it << '\n';
        }
    }

    return 0;
}

7. Код на Python 3

n = int(input())

counts = {}
min_heap = []
max_heap = []

import heapq

for _ in range(n):
    parts = input().split()
    t = int(parts[0])

    if t == 1:
        x = int(parts[1])
        counts[x] = counts.get(x, 0) + 1
        heapq.heappush(min_heap, x)
        heapq.heappush(max_heap, -x)

    elif t == 2:
        x = int(parts[1])
        counts[x] -= 1
        if counts[x] == 0:
            del counts[x]

    elif t == 3:
        while min_heap and min_heap[0] not in counts:
            heapq.heappop(min_heap)
        print(min_heap[0])

    else:
        while max_heap and (-max_heap[0]) not in counts:
            heapq.heappop(max_heap)
        print(-max_heap[0])