对每个元素统计它前面值为它二倍的元素个数。统计前/后比它大/小个数用BIT，思路和315. Count of Smaller Numbers After Self一样。BIT能在元素可mutable的要求下以O(lgN)时间求presum，树的每个index对应元素值，里头存的是元素值当前的个数。因此只要根据元素值大小对应到BIT的index，然后对任意想查的元素找到对应的index后，就能以O(lgN)算出所有index和index前（比它大/小）的和（总个数）。这道题比315在查index上麻烦了点，从后往前遍历的话，需要找不超过当前元素值1/2的最大值，用二分法，再用值查对应的index。
/*
* @lc app=leetcode id=493 lang=cpp
*
* [493] Reverse Pairs
*
* https://leetcode.com/problems/reverse-pairs/description/
*
* algorithms
* Hard (23.52%)
* Likes: 613
* Dislikes: 91
* Total Accepted: 28.5K
* Total Submissions: 120.1K
* Testcase Example: '[1,3,2,3,1]'
*
* Given an array nums, we call (i, j) an important reverse pair if i < j and
* nums[i] > 2*nums[j].
*
* You need to return the number of important reverse pairs in the given
* array.
*
* Example1:
*
* Input: [1,3,2,3,1]
* Output: 2
*
*
* Example2:
*
* Input: [2,4,3,5,1]
* Output: 3
*
*
* Note:
*
* The length of the given array will not exceed 50,000.
* All the numbers in the input array are in the range of 32-bit integer.
*
*
*/
// @lc code=start
class Solution {
public:
class BIT {
public:
vector<int> sums;
BIT(const int N): sums(N + 1, 0) {};
static inline int lowbit(int x) {return x & (-x);}
void update(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}
int query(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}
};
int reversePairs(vector<int>& nums) {
const int N = nums.size();
vector<int> v(nums);
sort(v.begin(), v.end());
unordered_map<int, int> indices;
for (int i = 0; i < N; ++i) {
indices[v[i]] = i + 1;
}
int res = 0;
BIT tree(N);
for (int i = N - 1; i >= 0; --i) {
res += tree.query(lower_bound(v.begin(), v.end(), nums[i] / 2.0) - v.begin());
tree.update(indices[nums[i]], 1);
}
return res;
}
};
// @lc code=end