int ans = 0;
//[l,r)
void merge_sort(vector<int>&A, int l, int r, int *T)
{
if(r-l >1)
{
int mid = l+(r-l)/2;
int ll = l, rr = mid,i = l;
merge_sort(A, l, mid, T);
merge_sort(A, mid, r, T);
while(ll<mid || rr < r)
{
if(rr>=r || (ll<mid && A[ll]<=A[rr]))
T[i++]=(A[ll++]);
else {
T[i++]=(A[rr++]);
ans += mid - ll;
}
}
for(int i = l;i < r;i ++)
A[i] = T[i];
}
return;
}
int InversePairs(vector<int> data) {
int * tmp = new int[data.size() + 10];
merge_sort(data, 0, data.size(),tmp);
return ans;
} 
京公网安备 11010502036488号