Description
Given an integer array nums, return an integer array counts where \(counts[i]\) is the number of smaller elements to the right of \(nums[i]\).
Constraints
- \(1 \le nums.length \le 10^5\)
- \(-10^4 \le nums[i] \le 10^4\)
Solution
模板题，回顾一下也好
Code
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
constexpr size_t N = 5e4;
constexpr int shift = 1 + 1e4;
int ft[N];
memset(ft, 0, sizeof ft);
vector<int> ans;
for(auto iter = nums.rbegin(); iter != nums.rend(); iter++) {
int v = *iter + shift;
int sum = 0;
for(int u = v-1; u; u -= u&-u) sum+=ft[u];
ans.push_back(sum);
for(; v < N; v += v&-v) ft[v]++;
}
reverse(ans.begin(), ans.end());
return ans;
}
};