6.19刷题打卡

题目 数组中的逆序对

最爱的树状数组

    int mod = (int) 1e9 + 7;
    public int InversePairs (int[] nums) {
        // write code here
        int[] a = nums.clone();
        Arrays.sort(a);
        int n = a.length;
        int[] t = new int[n + 1];
        long ans = 0;
        for (int v: nums) {
            int l = 0, r = n - 1;
            while (l <= r) {
                int m = l + r >> 1;
                if (a[m] < v) l = m + 1;
                else r = m - 1;
            }
            l = n - l; // 0 ~ n - 1 -> 1 ~ n
            ans = (ans + find(t, l)) % mod;
            add(t, l);
        }
        return (int) ans;
    }
    void add(int[] t, int i) {
        while (i < t.length) {
            t[i]++;
            i += i & -i;
        }
    }
    long find(int[] t, int i) {
        long ans = 0;
        while (i > 0) {
            ans += t[i];
            i -= i & -i;
        }
        return ans;
    }

打卡截图