| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | nor | 157 |
| 3 | cry | 157 |
| 5 | atcoder_official | 156 |
| 6 | -is-this-fft- | 155 |
| 7 | maroonrk | 154 |
| 7 | adamant | 154 |
| 9 | Um_nik | 153 |
| 10 | Petr | 146 |
Дана перестановка длинны n ≤ 10^5. Каждый её элемент раскрашен в один из n цветов. Необходимо для каждого элемента i найти количество инверсий одного с ним цвета. Ожидаемая сложность n log(n).
Кроме очевидного "для каждого цвета взять дерево отрезков и посчитать инверсии" мне в голову ничего не приходит. Что ещё можно попробовать?
Что имеется ввиду под "инверсии одного с ним цвета"?
Есть перестановка p и массив c ( c[i] <= n ). Найти количество пар p[i], p[j], что:
p[i] > p[j]
i < j
c[i] = c[j]
Если я правильно понял, то как-то так.
А почему не подходит просто, как было написано, "для каждого цвета взять дерево отрезков и посчитать инверсии"? Перебираем все цвета, потом смотрим элементы только с этим цветом и считаем инверсии, потом чистим структуру, с помощью которой мы это считали. Важно, чтобы очистка происходила за $$$O(cnt_{col})$$$, где $$$cnt_{col}$$$ — количество элементов цвета $$$col$$$. Вот мы и получили $$$O(NlogN)$$$.
Единственный известный мне способ подсчёта инверсий при помощи дерева следующий: tab[i] — количество инверсий для i-того элемента.
Задаем size=n+1, далее идём по массиву в порядке возрастания индексов: tab[i]=t.sum(p[i]+1, n); t.upd(p[i]);
Если сначала отсортировать пары (p[i], c[i]) (stable_sort) по цвету, а затем находить инверсии для каждого цвета по-отдельности, то обнулять val дерева придётся O(n) раз, итого O(n*n).
Если же для каждого цвета выделить своё дерево, то тогда по памяти выходит O(n*n).
Или инверсии можно находить иначе?
А что насчёт задачи нахождения общего количества одноцветных инверсий? Может она проще решается?
Можно заметить, что мы делаем для каждого цвета $$$O(cnt_{col})$$$ вызовов функции $$$t.upd()$$$, а также несложно понять, что $$$\sum_{col \in colors}{cnt_{col}} = N$$$, где $$$cnt_{col}$$$ — количество элементов с цветом $$$col$$$. То есть, мы для каждого цвета сначала можем проходиться и добавлять в Фенвик эти элементы, а потом снова пройтись по этим же элементам и удалих их из Фенвика. Итого $$$O(NlogN)$$$, а не $$$O(N^2)$$$