1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> countSmaller(std::vector<int>& nums) {
        nums = Discretize(nums);
        int n = nums.size();
        tree_.resize(n + 1, 0);
        
        std::vector<int> res;
        res.reserve(n);
        
        for (int i = n - 1; i >= 0; --i) {
            res.push_back(Query(nums[i] - 1));
            Add(nums[i], 1);
        }
        
        std::reverse(res.begin(), res.end());
        return res;
    }
    
private:
    static int LowBit(int x) {
        return x & (-x);
    }
    
    void Add(int idx, int delta) {
        while (idx < tree_.size()) {
            tree_[idx] += delta;
            idx += LowBit(idx);
        }
    }
    
    int Query(int idx) const {
        int sum = 0;
        while (idx > 0) {
            sum += tree_[idx];
            idx -= LowBit(idx);
        }
        return sum;
    }
    
    std::vector<int> Discretize(const std::vector<int>& nums) {
        std::vector<int> sorted_nums(nums);
        std::sort(sorted_nums.begin(), sorted_nums.end());
        auto last = std::unique(sorted_nums.begin(), sorted_nums.end());
        sorted_nums.erase(last, sorted_nums.end());
        
        std::vector<int> ranks;
        ranks.reserve(nums.size());
        
        for (int num : nums) {
            int rank = std::lower_bound(sorted_nums.begin(), sorted_nums.end(), num) - sorted_nums.begin();
            ranks.push_back(rank + 1);
        }
        
        return ranks;
    }
    
    std::vector<int> tree_;
};