Блог пользователя vintage_Vlad_Makeev

Автор vintage_Vlad_Makeev, 10 лет назад, По-русски

Здравствуйте!

Возникла вот такая задачка: надо добавлять\удалять элементы из массива и при этом уметь быстро отвечать на вопрос о k порядковой статистике. С одной стороны, тут должен сет пройти, но с другой,насколько я знаю, итераторы в сете реализованы на подобии двусвязного списка, поэтому кроме k инкриметнов итераторов ничего не выйдет.

Что тут можно побыстрее засунуть? Спасибо!

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

sqrt-декомпозиция

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Злобно заминусовали... А ведь я обычно именно такое решение пишу) И ограничения обычно достаточно лояльные, чтобы это заходило.

    Можно вообще на векторах все это написать, со стандартными операциями, и кода получится очень мало. После вставки элемента попытаться пропихнуть лишнее вверх, после удаления попытаться вытащить лишнее сверху. А ответ на запрос будет в блоке query/block_size на позиции query%block_size.

    И немного оффтопа — можно отметить, что есть целый класс задач, в которых это проходит, а привычное дерево отрезков — нет. У нас ведь get за О(1). Попробуйте скормить дереву отрезков задачу о k-ой порядковой статистике, в которой запросов 100 миллионов, с дополнительным условием о том, что update-запросов среди них не более 100 тысяч.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно либо структурами из SGI STL (статья), либо деревом отрезков (статья). Либо свой сбалансированный бинарник написать, дерамиду, например.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Если числа небольшие, можно решать деревом Фенвика. Если числа большие, то иногда можно сжать их (т.е. посортировать и присвоить первому по возрастанию значение 1, второму — 2 и т.д.), но это не всегда допустимо. Можно просто вместо массива в дереве Фенвика использовать map/unordered_map, чтобы не создавать лишнего.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Об общем случае задачи уже написали выше.

Для частного случая, когда K фиксировано, можно решать с помощью 2 set'ов (первый для K минимальных чисел и второй для всего остального). Еще популярная похожая задача, когда запрос "найти медиану", т.е. K равно половине текущего размера, тогда тоже можно с помощью 2 set'ов, только их размеры нужно балансировать между операциями — если какой-то стал на 2 больше другого, то перебросить крайний элемент.