在数组中的两个数字，
如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
这道题比较简单的方法是利用归并排序，不过本题的本意是区间查询，那么既然是区间查询树状数组自然是可以解决的，当然由于本题数据过大树状数组需要离散化，这里我们把数据离散化到1~n。
那么该怎么查询呢？首先将nums数组放到一个临时数组tmp中，对其进行排序，然后我们从后往前进行遍历，首先找到nums数组在tmp数组的下标,然后根据下标进行查找（树状数组中求和可以看作该元素二进制减一的元素前缀和），查找完毕加入该元素，遍历完整个数组即可。
class Solution {
#define Max 100005
int c[Max];
void init(){
memset(c,0,sizeof(c));
}
int low_bit(int x){
return x&(-x);
}
void add(int x,int maxv,int d){
while(x<=maxv){
c[x]+=d;
x+=low_bit(x);
}
}
int sum(int x){
int s=0;
while(x>0){
s+=c[x];
x-=low_bit(x);
}
return s;
}
int bin(vector<int>& tmp,int v){
int l=0,r=tmp.size()-1;
while(l<=r){
int mid=l+((r-l)>>1);
if(tmp[mid]<v){
l=mid+1;
}else if(tmp[mid]>v){
r=mid-1;
}else {
return mid;
}
}
return -1;
}
public:
int reversePairs(vector<int>& nums) {
init();
vector<int> tmp;
for(int i=0;i<nums.size();++i){
tmp.push_back(nums[i]);
}
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
int ans=0;
for(int i=nums.size()-1;i>=0;--i){
int idx=bin(tmp,nums[i])+1;
//找到nums[i]在tmp数组的下标+1，树状数组要求下标从1开始
ans+=sum(idx-1);
//既然我们把数据离散化成1~n，那么求和就是树状数组中下标-1元素的前缀和了
add(idx,nums.size(),1);
//求和完毕加入
}
return ans;
}
};
给定一个数组 nums ，
如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1]
输出: 2
示例 2:
输入: [2,4,3,5,1]
输出: 3
注意:
给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。
这道题跟上一道题几乎一样，不过还是有些不同的地方。
首先就是因为数组数据是在int32之内，但是我们查找肯定是要把数据*2的，这样就会造成数据溢出而出现错误，所以这里tmp数组我们要定义为longlong。
具体的操作也有不同，在临时数组tmp中我们不仅要加入nums[i]，还要加入nums[i]*2，其中nums[i]是我们求和的标准，nums[i]*2是我们加入到树状数组的指标也即是我们查找的标准。也就是说在求和的时候我们求取nums[i]的和，加入树状数组的时候我们加入的是nums[i]*2。
class Solution {
#define Max 100005
#define ll long long
int c[Max];
void init(){
memset(c,0,sizeof(c));
}
int low_bit(int x){
return x&(-x);
}
void add(int x,int maxv,int d){
while(x<=maxv){
c[x]+=d;
x+=low_bit(x);
}
}
int sum(int x){
int s=0;
while(x){
s+=c[x];
x-=low_bit(x);
}
return s;
}
int bin(vector<ll>& tmp,ll v){
int l=0,r=tmp.size()-1;
while(l<=r){
int mid=l+((r-l)>>1);
if(tmp[mid]<v){
l=mid+1;
}else if(tmp[mid]>v){
r=mid-1;
}else {
return mid;
}
}
return -1;
}
public:
int reversePairs(vector<int>& nums) {
init();
vector<ll> tmp;
for(int i=0;i<nums.size();++i){
tmp.push_back(nums[i]);
tmp.push_back((ll)nums[i]*2);
}
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
ll ans=0;
for(int i=nums.size()-1;i>=0;--i){
int idx=bin(tmp,nums[i])+1;
ans+=sum(idx-1);
add(bin(tmp,(ll)nums[i]*2)+1,tmp.size(),1);
}
return ans;
}
};