Cacher is the code snippet organizer for pro developers

public class Solution {
   
    class TreeNode{
        long val;
        int dup;
        int count;
        TreeNode left;
        TreeNode right;
        TreeNode(long v){
            left = null;
            right = null;
            val = v;
            dup = 1;
            count = 0;
        }
    }
    
    private void insert(TreeNode root, long val){
        while(true){
            if(root.val<val){
                root.count++;
                if(root.right==null) {
                    root.right = new TreeNode(val);
                    return;
                }else{
                    root = root.right;
                }
            }else if(root.val==val){
                root.dup++;
                return;
            }else{
                if(root.left==null){
                    root.left = new TreeNode(val);
                    return;
                }else{
                    root = root.left;
                }
            }
        }
    }
    
    private int search(TreeNode root, long target){
        if(root==null) return 0;
//        System.out.println(root.val+" "+target);
        if(target<root.val) return root.count+root.dup+search(root.left,target);
        else if(target==root.val) return root.count+search(root.left,target);
        return search(root.right,target);
    }
    
    public int reversePairs(int[] nums) {
        TreeNode root = new TreeNode(Integer.MIN_VALUE);        
        int ret = 0;
        for(int x:nums) {
            ret+=search(root.right,(long)2*x);
            insert(root,(long)x);
        }   
        return ret;
    }
}

public class Solution {

    int[] sorted;
    private int[] merge(int[] nums, int s1, int e1, int s2, int e2){
        int[] ret = new int[e1-s1+1+e2-s2+1];
        int a = s1;
        int b = s2;
        int ind = 0;
        while(a<=e1 || b<=e2){
            if(a==e1+1){
                while(b<=e2) ret[ind++] = nums[b++];
                break;
            }
            if(b==e2+1){
                while(a<=e1) ret[ind++] = nums[a++];
                break;
            }
            if(nums[a]<nums[b]){
                ret[ind++] = nums[a++];
            }else ret[ind++] = nums[b++];
        }
        return ret;
    }
    
    private int mergeSort(int[] num, int start, int end){
        if(start==end){
            sorted[start] = num[start];
            return 0;
        }
        if(start==end-1){            
            sorted[start] = Math.min(num[start],num[end]);
            sorted[end] = Math.max(num[start],num[end]);
            if((long)num[start]>(long)num[end]*2) return 1;
            return 0;
        }
        int mid = (end-start)/2+start;
        int ret = mergeSort(num,start,mid)+mergeSort(num,mid+1,end);
        int left = start;
        int right = mid+1;
        while(left<=mid && right<=end){
            if((long)sorted[left]>(long)2*sorted[right]){
                ret+=mid-left+1;
//                System.out.println(left+" "+sorted[left]+" "+right+" "+sorted[right]);
                right++;
            }else left++;
        }
        
        int[] tmp = merge(sorted,start,mid,mid+1,end);
        int ind = start;
        for(int x:tmp) sorted[start++] = x;
        return ret;
    }
    
    public int reversePairs(int[] nums) {
        if(nums.length==0) return 0;
        sorted = new int[nums.length];
        return mergeSort(nums,0,nums.length-1);
    }
}

public class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] helper = new int[nums.length];
        return countWhileMergeSort(nums, helper, 0, nums.length - 1);
    }
    
    private int countWhileMergeSort(int[] nums, int[] helper, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int leftCount = countWhileMergeSort(nums, helper, left, mid);
        int rightCount = countWhileMergeSort(nums, helper, mid + 1, right);
        int i = left, j = mid + 1;
        int count = leftCount + rightCount;
        while (i <= mid && j <= right) {
            if (nums[i] > 2L * nums[j]) {
                count += mid + 1 - i;  // !!!!! based on the sorted array property
                j++;
            } else {
                i++;
            }
        }
        
        // merge
        for (i = left; i <= right; i++) {
            helper[i] = nums[i];
        }
        i = left;
        j = mid + 1;
        int k = left;
        while (i <= mid && j <= right) {
            if (helper[i] <= helper[j]) {
                nums[k++] = helper[i++];
            } else {
                nums[k++] = helper[j++];
            }
        }
        while (i <= mid) {
            nums[k++] = helper[i++];
        }
        // System.out.println(Arrays.toString(nums));
        // System.out.printf("[%d, %d], count=%d\n", left, right, count);
        return count;
    }
}

public class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length-1);
    }
    private int mergeSort(int[] nums, int s, int e){
        if(s>=e) return 0; 
        int mid = s + (e-s)/2; 
        int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); 
        for(int i = s, j = mid+1; i<=mid; i++){
            while(j<=e && nums[i]/2.0 > nums[j]) j++; 
            cnt += j-(mid+1); 
        }
        Arrays.sort(nums, s, e+1); 
        return cnt; 
    }
}