c++ wighted random, O(logn) for pick()
\nclass Solution {\npublic:\n    Solution(vector<vector<int>> rects):rects(rects) {\n\n        sum = 0;\n        \n        for(auto& e : rects){\n            \n
```\nclass Solution {\npublic:\n    Solution(vector<vector<int>> rects):rects(rects) {\n\n        sum = 0;\n        \n        for(auto& e : rects){\n            \n            const auto row = e[2]-e[0]+1;\n            const auto col = e[3]-e[1]+1;\n            \n            sum += row*col;\n            \n            dp.push_back(sum);\n        }\n    }\n    \n    vector<int> pick() {\n        \n        const auto r = rand() % sum;\n        \n        const auto it = std::upper_bound(begin(dp), end(dp), r);\n\n        const auto index = std::distance(dp.begin(), it);\n        \n        const auto row = (rects[index][3]-rects[index][1]) +1;\n        const auto col = (rects[index][2]-rects[index][0]) +1;\n        \n        const auto x = rects[index][0] + rand()%col;\n        const auto y = rects[index][1] + rand()%row;\n        \n        return {x, y};\n    }\n    \nprivate:    \n    vector<vector<int>> rects;\n    int sum;\n    std::vector<int> dp;\n};\n```
[]