493

reversepair.cpp

class BIT
{
private:
    vector<int> tree;
    int n;
public:
    BIT(int n): n(n), tree(n+1){}
    static constexpr int lowbit(int x) {return x & (-x);}
    void update(int x, int d)
    {
        while(x <= n)
        {
            tree[x] += d;
            x += lowbit(x);
        }
    }

    int query(int x) const 
    {
        int ans = 0;
        while(x)
        {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
};


class Solution {
public:
    int reversePairs(vector<int>& nums) {
        set<long long> allNUmbers;
        for(int x: nums)
        {
            allNUmbers.insert(x);
            allNUmbers.insert((long long)x*2);
        }
        // 利用哈希表进行离散化
        unordered_map<long long, int> values;
        int idx = 0;
        for(long long x:allNUmbers) values[x] = ++idx;

        int ret = 0;
        BIT bit(values.size());
        for(int i =0; i < nums.size(); i++)
        {
            int left = values[(long long)nums[i] * 2], right = values.size();
            ret += bit.query(right) - bit.query(left);
            bit.update(values[nums[i]], 1);
        }
        return ret;
    }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

int main() {
    string line;
    while (getline(cin, line)) {
        vector<int> nums = stringToIntegerVector(line);
        
        int ret = Solution().reversePairs(nums);

        string out = to_string(ret);
        cout << out << endl;
    }
    return 0;
}