| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Здравствуйте!
Возникла вот такая задачка: надо добавлять\удалять элементы из массива и при этом уметь быстро отвечать на вопрос о k порядковой статистике. С одной стороны, тут должен сет пройти, но с другой,насколько я знаю, итераторы в сете реализованы на подобии двусвязного списка, поэтому кроме k инкриметнов итераторов ничего не выйдет.
Что тут можно побыстрее засунуть? Спасибо!
sqrt-декомпозиция
Злобно заминусовали... А ведь я обычно именно такое решение пишу) И ограничения обычно достаточно лояльные, чтобы это заходило.
Можно вообще на векторах все это написать, со стандартными операциями, и кода получится очень мало. После вставки элемента попытаться пропихнуть лишнее вверх, после удаления попытаться вытащить лишнее сверху. А ответ на запрос будет в блоке query/block_size на позиции query%block_size.
И немного оффтопа — можно отметить, что есть целый класс задач, в которых это проходит, а привычное дерево отрезков — нет. У нас ведь get за О(1). Попробуйте скормить дереву отрезков задачу о k-ой порядковой статистике, в которой запросов 100 миллионов, с дополнительным условием о том, что update-запросов среди них не более 100 тысяч.
Можно либо структурами из SGI STL (статья), либо деревом отрезков (статья). Либо свой сбалансированный бинарник написать, дерамиду, например.
Если числа небольшие, можно решать деревом Фенвика. Если числа большие, то иногда можно сжать их (т.е. посортировать и присвоить первому по возрастанию значение 1, второму — 2 и т.д.), но это не всегда допустимо. Можно просто вместо массива в дереве Фенвика использовать map/unordered_map, чтобы не создавать лишнего.
Спасибо большое!
Об общем случае задачи уже написали выше.
Для частного случая, когда K фиксировано, можно решать с помощью 2 set'ов (первый для K минимальных чисел и второй для всего остального). Еще популярная похожая задача, когда запрос "найти медиану", т.е. K равно половине текущего размера, тогда тоже можно с помощью 2 set'ов, только их размеры нужно балансировать между операциями — если какой-то стал на 2 больше другого, то перебросить крайний элемент.
А ещё, помнится, где-то тут обсуждали совсем уж общий случай — K-ую статистику на подотрезке... :)
Было дело...