Решая задачу 1042D - Петя и массив, столкнулся с приведенной в заголовке проблемой. В редакционной статье написано, что это можно реализовать используя дерево Фенвика или дерево отрезков. В просторах интернета реализацию Фенвика или дерева отрезков именно для этой задачи не нашел.
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 8 | ecnerwala | 3494 |
| 9 | Um_nik | 3396 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | -is-this-fft- | 161 |
| 3 | maomao90 | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 04.10.2024 12:24:34 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Для каждого элемента нужно хранить его количество с помощью Фенвика или ДО. Теперь количество чисел меньших X, это сумма чисел на отрезке [0; X). (Сумма чисел на отрезке [X; X], это количество чисел X).
Реализация.
Конкретно для этой задачи тебе надо сжать все значения которые тебя интересуют и применить стандартный способ, который я описал выше.
Я сейчас объясню как можно делать с помощью дерево отрезков . Вот допустим у нас есть массив с числами 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 ) и т.д . Если хочешь узнать сколько меньше справа ,то начинаешь делать тоже самое только начиная с последнего элемента . Данную технику можешь применить в данной задаче и также в задачах на инверсию. Если будут вопросы ,пиши .
А если элементы идут не подряд, а условно с большим разбросом: 1 100 10000 100000 и тд, то по индексам обращаться не получиться.
Закодируй их, то есть всего чисел где-то 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]];
}
}
Ну можно еще сливать массивы в вершинах ДО и бинпоиском потом делать всю дичь, которую ты хочешь, но это не так быстро — (logN)^2 за операцию.
ordered_set
В сете можем только быстро найти итератор нужного элемента, а вот найти именно индекс элемента(это и будет кол-во чисел меньших этого) — нельзя
link