| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
Подскажите структуру данных(В этой структуре в некотором виде хранится список целых чисел (числа могут повторяться, априори порядок неважен)), для которой будут эффективно выполняться следующие операции:
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⌋ максимальных.
Тупые структуры данных как же я вас блин ненавижу
бор (префиксное дерево)