6043. 统计包含每个点的矩形数目

6043. 统计包含每个点的矩形数目

文章目录

• • 题目
  • 样例
  • 数据
  • 暴力 + 二分
  • 二维偏序问题：树状数组
  • Python
  • • 排序 + 双指针
    • 名次树：（SortedList）

---

题目

---

样例

输入：reclass="superseo">ctangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
输出：[1,3]
解释：
第一个矩形只包含点 (1, 1) 。
第二个矩形只包含点 (1, 1) 。
第三个矩形包含点 (1, 3) 和 (1, 1) 。
包含点 (1, 3) 的矩形数目为 1 。
包含点 (1, 1) 的矩形数目为 3 。
所以，我们返回 [1, 3] 。

---

数据

1 <= rectangles.length, points.length <= 5 * 104
rectangles[i].length == points[j].length == 2
1 <= li, xj <= 109
1 <= hi, yj <= 100
所有 rectangles 互不相同 。
所有 points 互不相同 。

---

暴力 + 二分

思路：

• 由于高度最大100，所以考虑以此为突破口。（高：y；长，x）
• 对每个y都存入对应矩阵的x，并排序。
• 对每个点都枚100次y，然后二分到大于x的位置，加上贡献。

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        vector<vector<int>> mp(110, vector<int>());
        for (auto &v: rectangles) mp[v[1]].push_back(v[0]);
        for (auto &v: mp) sort(v.begin(), v.end());

        vector<int> res;
        for (int i = 0; i < points.size(); i++) {
            auto &v = points[i];
            int a = v[0], b = v[1];
            int ans = 0;
            for (int j = 0; j < 110; j++) {
                auto &v = mp[j];
                if(!v.size() || j < b) continue;
                int d = lower_bound(v.begin(), v.end(), a) - v.begin();
                ans += v.size() - d;
            }
            res.push_back(ans);
        }
        return res;
    }
};

---

二维偏序问题：树状数组

思路：

• 打包矩阵和点 ( x , y , i ) {(x,y,i)} (x,y,i)，存入 v e c t o r {vector} vector中。（标记矩阵INF，点 i {i} i表示第 i {i} i个点）

• 排序完后，倒序遍历 v e c t o r {vector} vector

  • 排序按 x , y , i {x,y,i} x,y,i依次排序
  • 遍历到矩阵，就加进 t r {tr} tr数组中
  • 遍历到点，此时 t r {tr} tr数组中都是 > = x {>=x} >=x && > = y {>=y} >=y
  • a n s [ i ] = s u m ( n ) − s u m ( y − 1 ) {ans[i] = sum(n) - sum(y-1)} ans[i]=sum(n)−sum(y−1)

class Solution {
public:
    static constexpr int N = 110;
    int tr[N + 1] = {0};
    
    int lowbit(int x) {
        return x & -x;
    }
    
    void add(int x, int c) {
        for (int i = x; i <= N; i += lowbit(i)) tr[i] += c;
    }
    
    int sum(int x) {
        int res = 0;
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        vector<pair<pair<int, int>, int>> res;
        for (auto &v: rectangles) {
            res.push_back({{v[0], v[1]}, 0x3f3f3f3f});
        }
        for (int i = 0; i < points.size(); i++) {
            auto &v = points[i];
            res.push_back({{v[0], v[1]}, i});
        }
        sort(res.begin(), res.end());
        vector<int> ans(points.size());
        for (int i = res.size() - 1; i >= 0; i--) {
            auto &v = res[i];
            if(v.second == 0x3f3f3f3f) {
                add(v.first.second, 1);
            } else {
                ans[v.second] = sum(N) - sum(v.first.second - 1);
            }
        }
        return ans;
    }
};

---

Python 排序 + 双指针

参考灵茶山艾府

思路：

• 对矩阵和点都进行 y {y} y降序排列。
• 每次插完 x {x} x坐标后，对 x s {xs} xs进行排序，二分出 > = x {>=x} >=x的矩阵个数。
• 由于我们是按纵坐标从大到小遍历的，因此这些矩形的纵坐标均不小于 y {y} y。

class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        rectangles.sort(key=lambda r: -r[1])
        n = len(points)
        ans = [0] * n
        i, xs = 0, []
        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):
            start = i
            while i < len(rectangles) and y <= rectangles[i][1]:
                xs.append(rectangles[i][0])
                i += 1
            if start < i:
                xs.sort()  # 只有在 xs 插入了新元素时才排序
            ans[id] = i - bisect_left(xs, x)
        return ans

---

名次树：（SortedList）

如果x<=1e9 && y<=1e9

from sortedcontainers import SortedList

class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        rectangles.sort(key=lambda r: -r[1])
        n = len(points)
        ans = [0] * n
        i, xs = 0, SortedList()
        for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][1]):
            while i < len(rectangles) and y <= rectangles[i][1]:
                xs.add(rectangles[i][0])
                i += 1
            ans[id] = i - xs.bisect_left(x)
        return ans