leetcode315 Count of Smaller Numbers After Self

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 class Solution 
 4 {
 5 public:
 6     int sum(vector<int> & bit,int i)
 7     {
 8         int ans = 0;
 9         while (i) { ans += bit[i]; i -= i & -i; }
10         return ans;
11     }
12     void add(vector<int> & bit,int i,int x)
13     {
14         int n = bit.size() - 1;
15         while (i <= n) { bit[i] += x; i += i & -i; }
16     }
17     vector<int> countSmaller(vector<int>& nums) 
18     {
19         int n = nums.size();
20         vector<int> a(nums.begin(),nums.end()),b(nums.begin(),nums.end());
21         sort(a.begin(),a.end());
22         a.erase(unique(a.begin(),a.end()),a.end());
23         for (int i = 0; i < n; i++)
24             b[i] = lower_bound(a.begin(),a.end(),b[i]) - a.begin() + 1;
25         vector<int> bit(n + 1,0),ans(n,0);
26         for (int i = n - 1; i >= 0; i--)
27         {
28             add(bit,b[i],1);
29             ans[i] = b[i] == 1 ? 0 : sum(bit,b[i] - 1);
30         }
31         return ans;
32     }
33 };
34 int main()
35 {
36     vector<int> v;
37     v.push_back(5);
38     v.push_back(-1);
39     v.push_back(6);
40     v.push_back(1);
41     vector<int> ans = Solution().countSmaller(v);
42     for (auto it: ans) cout << it << " ";
43     cout << endl;
44     return 0;
45 }