数组中的逆序对
C++，归并排序的分治思想。
其实做完以后，不仅求出了逆序对，而且把整个数组也排序了。
分治的思想，将整个序列分成近似的两半，再细分，1/2—>1/4。。。直到一个子序列中只有一个元素：
不说了，有点烦2333。
class Solution {
public:
int InversePairs(vector<int> data) {
return Merge(data, 0, data.size() - 1) % 1000000007;
}
int Merge(vector<int> &data, int left, int right) {
if (left >= right)
return 0;
int mid = (left + right) / 2;
int left_ans = Merge(data, left, mid) % 1000000007;
int right_ans = Merge(data, mid + 1, right) % 1000000007;
int i = mid, j = right;
int cnt = 0;
vector<int> copy;
while (copy.size() < right - left + 1) {
if (j <= mid || (i >= left && data[i] > data[j])) {
cnt += (j - mid);
cnt %= 1000000007;
copy.push_back(data[i]);
i--;
}
else if (i < left || (j > mid && data[i] < data[j])) {
copy.push_back(data[j]);
j--;
}
}
for (i = left; i <= right; i++) {
data[i] = copy.back();
copy.pop_back();
}
return (left_ans + cnt + right_ans) % 1000000007;
}
};
