Sto usando la merge sort per risolvere oii_paletta. Il metodo che uso funziona per tutti i subtask, tranne l’ultimo, in cui il numero degli scambi necessari è sbagliato.
Questo è il codice che ho usato per il numero di scambi;
long long across(vector<int>::iterator begin, vector<int>::iterator middle, vector<int>::iterator end, vector<int> &temp) {
vector<int>::iterator i = begin, j = middle, k = temp.begin();
int inv = 0;
while(i != middle && j != end) {
if(*i <= *j) {
*(k++) = *(i++);
}
else {
*(k++) = *(j++);
inv += middle - i;
}
}
while(i != middle)
*(k++) = *(i++);
while(j != end)
*(k++) = *(j++);
for(i = temp.begin(), j = begin; i != k; i++, j++)
*j = *i;
return inv;
}
long long mergeNcount(vector<int>::iterator begin, vector<int>::iterator end, vector<int> &temp) {
int L = end - begin;
if(L < 2) return 0;
long long inv = mergeNcount(begin, begin + L/2, temp) + mergeNcount(begin + L/2, end, temp);
inv += across(begin, begin + L/2, end, temp);
return inv;
}