import java.util.concurrent.ExecutionException;
/**
*
0 1 2 3
*/
public class Solution {
public int InversePairs(
int []
array) {
if(
array ==
null ||
array.length ==
0) return
0;
return InversePairCore(
array,
0,
array.length -
1);
}
public int InversePairCore(
int array[],
int start,
int end) {
if(
end < start){
try {
throw
new Exception(
"end < start!");
} catch (Exception e) {
e.printStackTrace();
}
}
if(start ==
end) return
0;
int mid = start + (
end - start) /
2;
int leftCount = InversePairCore(
array, start,
mid) %
1000000007;
int rightCount = InversePairCore(
array,
mid +
1,
end) %
1000000007;
int i =
mid;
int j =
end;
int count =
0;
while (i >= start && j >
mid) {
if(
array[i] >
array[j]) {
count += j -
mid;
count = count %
1000000007;
--i;
}
else {
--j;
}
}
int tmp[] =
new int[
end-start+
1];
int k =
0;
int m = start;
int n =
mid+
1;
while (
true) {
if(m >
mid && n >
end) break;
if(m >
mid) {
for(
int kk = n; kk <=
end; ++kk) tmp[k++] =
array[kk];
break;
}
if(n >
end) {
for(
int kk = m; kk <=
mid; ++kk) tmp[k++] =
array[kk];
break;
}
if(
array[m] >
array[n]) {
tmp[k++] =
array[n++];
}
else {
tmp[k++] =
array[m++];
}
}
for(
int p =
0; p < k; ++p) {
array[start+p] = tmp[p];
}
return (leftCount + rightCount + count) %
1000000007;
}
}
