Daily question - leetcode497 - random points in non overlapping rectangle - prefix and - bisection

Original link

Note：

Larger area , The higher the probability of winning , Take a sample from a rectangle , Abscissa and ordinate independent , Just generate them randomly
But first determine which rectangle it is

In one dimension , Use a prefix and an array to record the area and
Generate one number at a time , It will fall into this one-dimensional array , Use bisection to find out which rectangle is the corresponding position

Prefixes and arrays are subscripts from 1 At the beginning , So the range of two points is 1 ~ n
Subtract one from the result of two Can be mapped to the matrix array of the given input

The code is as follows ：

class Solution {
    
public:
    int n;
    vector<vector<int>> rects;
    vector<int> sum;
    Solution(vector<vector<int>>& _rects) {
    
        sum.push_back(0);
        rects = _rects;
        n = rects.size();
        for(auto r: rects){
    
            int w = r[2] - r[0] + 1, h = r[3] - r[1] + 1;
            sum.push_back(sum.back() + w * h);
        }
    }
    
    vector<int> pick() {
    
        int k = rand() % sum.back() + 1;
        int l = 1, r = n;
        while(l < r){
    
            int mid = l + r >> 1;
            if(sum[mid] >= k)    r = mid;
            else    l = mid + 1;
        }
        auto t = rects[r - 1];
        int dx = t[2] - t[0] + 1, dy = t[3] - t[1] + 1;
        return {
    rand() % dx + t[0], rand() % dy + t[1]};

    }
};

/** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(rects); * vector<int> param_1 = obj->pick(); */