LeetCode 493 翻转对

题意：给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

---

思路：这题很典型的树状数组的应用，离散化数据后，倒序查询，插入数据。因为边界问题搞错了好几次。离散化后记得删除多余的元素。

---

C++代码：

class Solution {

public:

    static const int MAXN = 100010;

    int tree[MAXN];

    int lowbit(int x){

        return x & (-x);

    }

    void add(int i, int val){

        while(i < MAXN){

            tree[i] += val;

            i += lowbit(i);

        }

    }

    int getsum(int i){

        int sum = 0;

        while(i > 0){

            sum += tree[i];

             i -= lowbit(i);

        }

        return sum;

    }

    int reversePairs(vector<int>& nums) {

        vector<int> a = nums;

        sort(nums.begin(), nums.end());

        auto oldend = nums.end();

        auto newend = unique(nums.begin(), nums.end());

        nums.erase(newend, oldend);

        for(int i = 0; i < a.size(); i++){

            a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin() + 1;

        }

        cout << endl;

        int res = 0;

        for(int i = a.size() - 1; i >= 0; i--){

            int x = nums[a[i] - 1];

            int y = (x <= 0) ? (x / 2 - 1) : (x - 1) / 2; 

            int t;

            if(nums[0] > y) t = 0;

            else {

                auto it = lower_bound(nums.begin(), nums.end(), y);

                if(it != nums.end())

                    t = it - nums.begin() + 1;

                else{

                    t = nums.size();

                }

                if(nums[t - 1] > y)

                    t--;

            }

            res += getsum(t); 

            add(a[i], 1);

        }

        return res;

    }

};