| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
Подскажите структуру данных(В этой структуре в некотором виде хранится список целых чисел (числа могут повторяться, априори порядок неважен)), для которой будут эффективно выполняться следующие операции:
1) Добавление нового элемента
2) Удаление элемента с данным значением (не по индексу)
3) Поиск минимального, максимального элемента
4) Поиск медианного элемента
Автокомментарий: текст был обновлен пользователем Obk (предыдущая версия, новая версия, сравнить).
Декартово дерево.
UPD: Ещё можно это: C++ STL: Policy based data structures
Если все запросы известны заранее, то дерево отрезков / дерево фенвика / sqrt-декомпозиция. Последняя часто применяется в алгоритме Мо, так как добавление в эту структуру данных осуществляется за O(1), а ответ на запросы за корень.
Если запросы не известны заранее, то дерево фенвика на хеш-таблице, динамическое дерево отрезков.
Альтернативы: декартово дерево, sqrt-list (работает, обычно, в два раза медленнее декартового на ограничениях порядка 300к). (Правда, sqrt-list может обгонять декартово дерево для примитивных типов в два раза при оптимизациях компилятора в виде векторизации, так как все данные лежат последовательно).
Также в некоторых реализациях стандартной библиотеки C++ есть структура данных под такие запросы, называется дерево статистик. Также там есть несколько других полезных структур данных. Мануал.
Вполне хватит двух multiset'ов. Поддерживаем инвариант, что первый multiset хранит ⌈N / 2⌉ минимальных элементов, второй — ⌊N / 2⌋ максимальных.
Тупые структуры данных как же я вас блин ненавижу
бор (префиксное дерево)