Clean C++ Solutions using Segment Tree and Discretization


  • 0
    D
    #define lson l, m, rt << 1
    #define rson m + 1, r, rt << 1 | 1
    class Solution {
    public:
        int reversePairs(vector<int>& nums) {
            
            if (nums.size() < 2) return 0;
            
            set<long long> s;
            for (int num : nums) {
                s.insert(num);
                s.insert(num * 2L + 1);
            }
            unordered_map<long long, int> idxs;
            
            // discretization
            int n = 0;
            for (long long num : s) {
                idxs[num] = n++;
            }
           
            vector<long long> sums(n << 2);
            build(sums, 0, n - 1, 1);
            
            
            int res = 0;
            for (int num : nums) {
                
                int idx = idxs[num * 2L + 1];
                res += query(sums, idx, n - 1, 0, n - 1, 1);
                update(sums, idxs[num], 0, n - 1, 1);
            }
            return res;
        }
        
        void build(vector<long long>& sums, int l, int r, int rt) {
            sums[rt] = 0;
            if (l == r) return;
            int m = (l + r) >> 1;
            build(sums, lson);
            build(sums, rson);
        }
        
        void pushUp(vector<long long>& sums, int rt) {
            sums[rt] = sums[rt << 1] + sums[rt << 1 | 1];
        }
        
        void update(vector<long long>& sums, int idx, int l, int r, int rt) {
            if (l == r) {
                sums[rt]++;
                return;
            }
            int m = (l + r) >> 1;
            if (idx <= m) update(sums, idx, lson);
            else update(sums, idx, rson);
            pushUp(sums, rt);
        }
        
        int query(vector<long long>& sums, int L, int R, int l, int r, int rt) {
            if (L <= l && r <= R) return sums[rt];
            int m = (l + r) >> 1;
            int ret = 0;
            if (L <= m) ret += query(sums, L, R, lson);
            if (R > m) ret += query(sums, L, R, rson);
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.