Question link

My thought process : I thought like what we do in inversion count we add smaller numbers at index of fenwick and then count the sum from (sorted index+1 to n-1) , we can do same in this case like making array of (nums1[i] — nums2[i] — diff) and then finding the correct index (using binary search) at a particular i and then finding sum till that index to get count. but i guess i cant implement it correctly can u please help

Fenwicktree struct

struct fenwicktree{
    int n;
    vector<int> fn;
    
    void init(int _n){
        n = _n+1;
        fn.resize(n,0);
    } 
     
    void get(int x,int sum){
       for(x++;x<n;x+=(x&(-x))){
            fn[x] += sum;
        }
    }
    
    // sum from 1 to idx
    int _sum(int x){
        int ans = 0;
        for(x++;x>0;x-=(x&(-x))){
            ans += fn[x];
        }
        return ans;
    }
    
    int sum(int left , int right){
        return _sum(right) - _sum(left-1);
    }
};

Logic:

class Solution {
public:   
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
        int n = nums1.size();
        fenwicktree tree;
        tree.init(n);
        vector<pair<int,int>> v;
        vector<int> a;
        for(int i = 0 ; i < n ; i++){
            v.push_back({nums1[i]-nums2[i]-diff,i});
            a.push_back({nums1[i]-nums2[i]-diff});
        }
        
        sort(v.begin(),v.end());
        sort(a.begin(),a.end());
        
        int ans = 0;
        for(int i = 0 ; i  < n ; i++){
            int sum = v[i].first;
            int idx = v[i].second;
            
            int j = lower_bound(a.begin(),a.end(),sum+diff)-a.begin();
            ans += tree._sum(j);
            tree.get(idx,1);
        }
        return ans;
    }
};