[思维题]leetcode6043：统计包含每个点的矩形数目(medium)

题目：

题解：

本题的横坐标的范围最大达到了 1e9，而纵坐标的范围才 100，所以纵坐标才是本题的突破口。题目实质上问的是对于每一个点 (xi,yi)，求横纵坐标都大于等于 xi ,yi 的矩形个数。因此我们把 100 种纵坐标看成 100 行数据，然后将矩形的横坐标装入相应的行中，并使用排序来使行中的横坐标有序。最后我们遍历每一个点 (xi,yi)，从 yi 行出发到 100行，使用二分统计这些行中横坐标大于等于 xi 的矩形个数，这样就统计所有横纵坐标大于等于 xi yi 的举行个数了。

代码如下：

class Solution {
public:
    // 由于纵坐标只有100种，可以看成100行数据，然后记录这100行的矩形的横坐标
    // 这样对于每一个点(xi,yi)，我们仅需使用二分统计[yi,100]内横坐标大于等于xi的矩形个数，然后进行累加即可
    vector countRectangles(vector>& r, vector>& p) {   
        vector lines[101];
        // 将所有矩形的坐标存入lines
        for(auto &it:r)lines[it[1]].push_back(it[0]);
        // 将每一行的横坐标进行排序，便于二分查找
        for(auto &l:lines)sort(l.begin(),l.end());

        int n=p.size();
        vector res(n,0);
        // 开始统计每个点，在每一行中的矩形个数
        for(int i=0;i
                auto& line=lines[j];
                // 累加第j行中横坐标大于等于p[i][0]的个数
                res[i]+=line.end()-lower_bound(line.begin(),line.end(),p[i][0]);
            }
                
        return res;
    }
};