Reverse Pairs
Code
#include<iostream>
#include<vector>
using namespace std;
int ans=0;
void merge(vector<int> &nums,int left,int mid,int right){
int p1=left,p2=mid+1;
vector<int> tmp;
while(p1<=mid && p2<=right){
if(nums[p1]<=nums[p2]){
tmp.push_back(nums[p1++]);
}else{
tmp.push_back(nums[p2++]);
ans+=mid-p1+1;
}
}
while(p1<=mid) tmp.push_back(nums[p1++]);
while(p2<=right) tmp.push_back(nums[p2++]);
int j=0;
for(int i=left;i<=right;++i){
nums[i]=tmp[j++];
}
}
void merge_sort(vector<int> &nums,int left,int right){
if(left==right) return;
int mid=left+(right-left)/2;
merge_sort(nums,left,mid);
merge_sort(nums,mid+1,right);
merge(nums,left,mid,right);
}
int reversePairs(vector<int> &nums){
int n=nums.size();
if(n<2) return 0;
merge_sort(nums,0,n-1);
return ans;
}
int main(){
vector<int> nums={2,1,4,5,3,7,9,8};
cout<<reversePairs(nums)<<endl;
exit(0);
}
