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

Как быстро находить кол-во элементов меньших заданного?
Автор Taobaomao, история, 6 лет назад, По-русски

Решая задачу 1042D - Petya and Array, столкнулся с приведенной в заголовке проблемой. В редакционной статье написано, что это можно реализовать используя дерево Фенвика или дерево отрезков. В просторах интернета реализацию Фенвика или дерева отрезков именно для этой задачи не нашел.

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

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

Для каждого элемента нужно хранить его количество с помощью Фенвика или ДО. Теперь количество чисел меньших X, это сумма чисел на отрезке [0; X). (Сумма чисел на отрезке [X; X], это количество чисел X).

Реализация.

Конкретно для этой задачи тебе надо сжать все значения которые тебя интересуют и применить стандартный способ, который я описал выше.

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

Я сейчас объясню как можно делать с помощью дерево отрезков . Вот допустим у нас есть массив с числами 2 5 6 3 4 1. И давай заведем еще один массив ,где мы будем отмечать used[x]=1 (если элемент X присутствует в массиве ) Допустим мы сейчас на элементе 2 . Мы должны найти сумму чисел от элемент 1 до элемент 1 в массиве used. Как видно ответ будет 0 . Сумму мы находим с помощью дерева отрезков . Потом делаем update used[2]=1. И в с помощью дерева отрезков делаем update ,пересчитываем сумму . Сейчас мы на элементе 5 . Смотрим сумму в массиве used ,от элемента 1 до 4 , ответ 1 (значит количество чисел меньше 5 ,это 1 ) и т.д . Если хочешь узнать сколько меньше справа ,то начинаешь делать тоже самое только начиная с последнего элемента . Данную технику можешь применить в данной задаче и также в задачах на инверсию. Если будут вопросы ,пиши .

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

    А если элементы идут не подряд, а условно с большим разбросом: 1 100 10000 100000 и тд, то по индексам обращаться не получиться.

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

      Закодируй их, то есть всего чисел где-то 200000 по порядку неубыванию задай каждому элементу индекс. Следовательно максимальный не превысит 200000

      КОД

      map<int,int>uncode,decode;

      int cnt=1;

      for(int i=1;i<=n;i++){

      if(uncode[a[i]]==0){

      uncode[a[i]]=cnt;

      a[i]=cnt;

      cnt++;

      }else{

      a[i]=uncode[a[i]];

      }

      }

      → Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Ну можно еще сливать массивы в вершинах ДО и бинпоиском потом делать всю дичь, которую ты хочешь, но это не так быстро — (logN)^2 за операцию.

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

ordered_set

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    В сете можем только быстро найти итератор нужного элемента, а вот найти именно индекс элемента(это и будет кол-во чисел меньших этого) — нельзя

    → Ответить