class Solution {
public:int reversePairs(vector<int>& record) {if(record.size()<1)return 0;int left,right;left=0;right=record.size()-1;int num=mergeSort(left,right,record);return num;}int mergeSort(int left,int right, vector<int>& record){if(left>=right)return 0;int mid;mid=left+(right-left)/2; int leftnum=mergeSort(left,mid,record);int rightnum=mergeSort(mid+1,right,record); int mergenum=merge(left,right,mid,record); return (leftnum+rightnum+mergenum);}int merge(int left,int right,int mid,vector<int>& record){int num=0;int i=left;int j=mid+1;vector<int> tmp;while(i<=mid && j<=right){if(record[i]>record[j]){num=mid-i+1+num;tmp.push_back(record[j++]);}elsetmp.push_back(record[i++]);}while(i<=mid){tmp.push_back(record[i++]);}while(j<=right){tmp.push_back(record[j++]);}for(int i=0;i<tmp.size();i++){record[left+i]=tmp[i];}return num;}};
class Solution {
public:int reversePairs(vector<int>& record) {int num=0;for(int step=1;step<record.size();step*=2){int leftmin,leftmax,rightmin,rightmax;for(leftmin=0;leftmin+step<record.size();leftmin=rightmax){leftmax=rightmin=leftmin+step;rightmax=leftmax+step;if(rightmax>record.size())rightmax=record.size();int start=leftmin;vector<int> tmp;while(leftmin<leftmax && rightmin<rightmax){if(record[leftmin]<=record[rightmin]){tmp.push_back(record[leftmin++]);}else{tmp.push_back(record[rightmin++]);num = num+leftmax-leftmin;}}while(leftmin<leftmax){tmp.push_back(record[leftmin++]);}while(rightmin<rightmax){tmp.push_back(record[rightmin++]);}for(int i=0;i<tmp.size();i++){record[start+i]=tmp[i];}}}return num;}};
