Дана перестановка длинны n ≤ 10^5. Каждый её элемент раскрашен в один из n цветов. Необходимо для каждого элемента i найти количество инверсий одного с ним цвета. Ожидаемая сложность n log(n).

Кроме очевидного "для каждого цвета взять дерево отрезков и посчитать инверсии" мне в голову ничего не приходит. Что ещё можно попробовать?