題意：給定一個數(shù)組?nums?，如果?i < j?且?nums[i] > 2*nums[j]?我們就將?(i, j)?稱作一個重要翻轉(zhuǎn)對。

你需要返回給定數(shù)組中的重要翻轉(zhuǎn)對的數(shù)量熬甫。

思路：這題很典型的樹狀數(shù)組的應(yīng)用缸浦，離散化數(shù)據(jù)后，倒序查詢锨咙，插入數(shù)據(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;

????}

};