题目
样例
输入：rectangles = [[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)，存入vector中。（标记矩阵INF，点i表示第i个点）
排序完后，倒序遍历vector
排序按x,y,i依次排序
遍历到矩阵，就加进tr数组中
遍历到点，此时t r {tr}tr数组中都是>=x &&>=y
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
