題目:
https://leetcode.com/problems/reverse-pairs/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public:
int arr[50005];
int help[50005];
int reversePairs(vector<int>& nums) {
for(int i=0; i<nums.size(); ++i) arr[i] = nums[i];
return count(0, nums.size()-1);
}
int count(int l, int r){
if(l == r) return 0;
int m = (l+r)/2;
return count(l, m) + count(m+1, r) + merge(l, m, r);
}
int merge(int l, int m, int r){
int ans = 0;
for(int i = l, j=m+1; i<=m; ++i){
while(j <= r && (long)arr[i] > (long)arr[j]*2){
j++;
}
ans += j - m - 1;
}
int i = l;
int a = l;
int b = m+1;
while(a <= m && b <= r){
help[i++] = (arr[a] <= arr[b]) ? arr[a++] : arr[b++];
}
while(a <= m){
help[i++] = arr[a++];
}
while(b <= r){
help[i++] = arr[b++];
}
for(int i=l; i <= r; ++i){
arr[i] = help[i];
}
return ans;
}
};
|
