Cặp nghịch đảo (Reverse Pairs) trong C++

Ví dụ

[2,8,7,7,2] → 3.

Merge Sort biến đổi

Trong merge, khi hợp nhất 2 nửa đã sắp xếp, dùng con trỏ first đếm số phần tử bên phải thỏa 2*right < left. Cộng vào đáp án. Phức tạp O(n log n).

Chương trình C++

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

class Solution {
    lli ans = 0;
    void merge(vector<int>& a, lli l, lli m, lli r) {
        vector<lli> tmp(r-l+1);
        lli i=l, j=m+1, p=0, first=m+1;
        while(i<=m) {
            while(first<=r && (lli)a[first]*2 < (lli)a[i]) first++;
            while(j<=r && a[j]<=a[i]) tmp[p++] = a[j++];
            ans += first - (m+1);
            tmp[p++] = a[i++];
        }
        while(j<=r) tmp[p++] = a[j++];
        for(lli i=l, p=0; i<=r; i++, p++) a[i] = tmp[p];
    }
    void calc(vector<int>& a, lli l, lli r) {
        if(l>=r) return;
        lli m = l + (r-l)/2;
        calc(a,l,m); calc(a,m+1,r);
        merge(a,l,m,r);
    }
public:
    int reversePairs(vector<int>& nums) {
        ans=0; calc(nums,0,nums.size()-1); return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,8,7,7,2};
    cout << ob.reversePairs(v); // 3
    return 0;
}