คู่ผกผันย้อนกลับ (Reverse Pairs) ใน C++

ภาพรวมปัญหา

มีอาร์เรย์ หาจำนวนคู่ (i, j) ที่ i < j และ nums[i] > 2 × nums[j] เรียกว่า important reverse pairs

ตัวอย่าง

[2,8,7,7,2] → Output: 3

แนวทางแก้ปัญหา (Merge Sort + Counting)

ปรับ Merge Sort: ในขั้น merge นับจำนวน pairs ที่ left[i] > 2×right[j]
ใช้ two pointers: สำหรับแต่ละ left[i] หา right[j] แรกที่ 2×right[j] ≥ left[i]
จำนวน valid pairs = (mid+1) - first_valid_index
Complexity: O(n log n)

ตัวอย่างโปรแกรม

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

class Solution {
public:
    int ans = 0;
    
    void merge(vector<int> &a, lli low, lli mid, lli high) {
        lli k = high - low + 1;
        vector<lli> temp(k);
        lli i = low, j = mid + 1, k_idx = 0;
        lli first = mid + 1;
        
        while(i <= mid) {
            while(first <= high && (lli)a[first] * 2 < (lli)a[i]) first++;
            while(j <= high && a[j] <= a[i]) {
                temp[k_idx++] = a[j++];
            }
            ans += first - (mid + 1);
            temp[k_idx++] = a[i++];
        }
        
        while(j <= high) temp[k_idx++] = a[j++];
        
        k_idx = 0;
        for(lli idx = low; idx <= high; idx++) a[idx] = temp[k_idx++];
    }
    
    void calc(vector<int> &a, lli low, lli high) {
        if(low >= high) return;
        lli mid = low + (high - low) / 2;
        calc(a, low, mid);
        calc(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    
    lli solve(vector<int> &A) {
        ans = 0;
        lli n = A.size();
        calc(A, 0, n - 1);
        return ans;
    }
    
    int reversePairs(vector<int>& nums) {
        return solve(nums);
    }
};

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

Input

{2,8,7,7,2}