前缀和 + 二分 + 随机数

用前缀和算出所有矩形面积的累加，在0-最大面积和范围产生随机数，看当前随机数落在哪个矩形的前缀和区间内，

这样选定矩形，确定矩形是时候使用二分快速确定，确定好当前矩形后，在当前矩形区域生成随机数

矩形面积越大，前缀和所占面积越大，被选中的概率越大

C++ 代码

class Solution {
public:
    vector<vector<int>> recs;
    vector<long long> t;

    Solution(vector<vector<int>>& rects) {
        recs = rects;
        int n = rects.size();
        t.resize(n + 1);
        t[0] = 0;
        for(int i = 0; i < n; i++)
            t[i + 1] = t[i] + (long long)(rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
    }

    vector<int> pick() {
        int n = recs.size();
        int ans = rand() % t[n];
        int left = 1;
        int right = n;
        while(left < right)
        {
            int m = (left + right) / 2;
            if(t[m] > ans)
            //找第一个比当前值大的值，不能是等于，等于的话就不能均匀分配了。左闭右开
                right = m;
            else left = m + 1;
        }
        int x1 = recs[left - 1][0];
        int y1 = recs[left - 1][1];
        int x2 = recs[left - 1][2];
        int y2 = recs[left - 1][3];

        int xr = rand() % (x2 - x1 + 1) + x1;
        int yr = rand() % (y2 - y1 + 1) + y1;

        return {xr, yr};
    }
};