Reverse Pairs: นับคู่ย้อนกลับสำคัญใน C++

ปัญหา

กำหนดอาร์เรย์ หาจำนวน Important Reverse Pairs คือคู่ (i, j) ที่ i < j และ nums[i] > 2 × nums[j]

ตัวอย่าง: [2,8,7,7,2] → 3 คู่: (8,2), (7,2), (7,2) (indices: (1,4), (2,4), (3,4))

แนวคิด: Modified Merge Sort (Divide & Conquer)

นับคู่ข้ามกลาง (Cross Pairs) ระหว่าง Merge Step

Merge Step Modification

ปกติ Merge: รวม 2 sorted halves

นับ Reverse Pairs: สำหรับแต่ละ i ใน Left Half หา first ใน Right Half แรกที่ 2*right[first] < left[i]

while (i <= mid) {
    while (first <= high && 2LL * a[first] < a[i]) first++;
    ans += first - (mid + 1);
    // ... merge logic
}

โค้ด C++

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

class Solution {
    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 = 0;
        lli first = mid + 1;
        
        while (i <= mid) {
            // นับ reverse pairs: หา first ใน right half ที่ 2*a[first] < a[i]
            while (first <= high && (lli)a[first] * 2 < (lli)a[i]) {
                first++;
            }
            
            // Merge: copy smaller elements from right
            while (j <= high && a[j] <= a[i]) {
                temp[k++] = a[j++];
            }
            
            ans += first - (mid + 1);  // จำนวน valid pairs สำหรับ a[i]
            temp[k++] = a[i++];
        }
        
        while (j <= high) temp[k++] = a[j++];
        
        // Copy back
        k = 0;
        for (lli idx = low; idx <= high; idx++) {
            a[idx] = temp[k++];
        }
    }
    
    void mergeSort(vector<int>& a, lli low, lli high) {
        if (low >= high) return;
        lli mid = low + (high - low) / 2;
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
    
public:
    int reversePairs(vector<int>& nums) {
        ans = 0;
        mergeSort(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;
}

ความซับซ้อน

• Time: O(n log n) - เหมือน Merge Sort
• Space: O(n) - Temporary array

Input / Output

Input:  {2,8,7,7,2}
Output: 3

หมายเหตุ

ใช้ long long สำหรับการคูณ 2 เพื่อป้องกัน Overflow