| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 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⌋ максимальных.
Тупые структуры данных как же я вас блин ненавижу
бор (префиксное дерево)