Есть перестановка p и массив c ( c[i] <= n ). Найти количество пар p[i], p[j], что:

1. p[i] > p[j]

2. i < j

3. c[i] = c[j]

Если я правильно понял, то как-то так.

Единственный известный мне способ подсчёта инверсий при помощи дерева следующий: tab[i] — количество инверсий для i-того элемента.

struct{
    vector<int> val;
    int size;
    void upd(int k){
        while(k < size){val[k]++; k=k|(k+1);}
    }
    int psum(int r){
        int out=0;
        while(r>0){out+=val[r]; r=(r&(r+1))-1;}
        return out;
    }
    int sum(int l, inr r){return psum(r)-psum(l-1);}
}BiT;

Задаем 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).

Или инверсии можно находить иначе?

А что насчёт задачи нахождения общего количества одноцветных инверсий? Может она проще решается?