class Solution {
public int[] countRectangles1(int[][] rectangles, int[][] points) {
Arrays.sort(rectangles, (a, b) -> b[1] - a[1]);
var n = points.length;
var ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(ids, (i, j) -> points[j][1] - points[i][1]);
var ans = new int[n];
var xs = new ArrayList<Integer>();
var i = 0;
for (var id : ids) {
var start = i;
while (i < rectangles.length && rectangles[i][1] >= points[id][1])
xs.add(rectangles[i++][0]);
if (start < i) Collections.sort(xs); // 只有在 xs 插入了新元素时才排序
ans[id] = i - lowerBound(xs, points[id][0]);
}
return ans;
}
public int[] countRectangles2(int[][] rectangles, int[][] points) {
Arrays.sort(rectangles, (a, b) -> b[0] - a[0]);
var n = points.length;
var ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(ids, (i, j) -> points[j][0] - points[i][0]);
var ans = new int[n];
var cnt = new int[101];
var i = 0;
for (var id : ids) {
while (i < rectangles.length && rectangles[i][0] >= points[id][0])
++cnt[rectangles[i++][1]];
for (var j = points[id][1]; j < cnt.length; ++j)
ans[id] += cnt[j];
}
return ans;
}
public int[] countRectangles(int[][] rectangles, int[][] points) {
List<Integer>[] xs = new List[101];
Arrays.setAll(xs, e -> new ArrayList<>());
for (var r : rectangles) xs[r[1]].add(r[0]);
for (var x : xs) Collections.sort(x);
var n = points.length;
var ans = new int[n];
for (var i = 0; i < n; ++i)
for (var j = points[i][1]; j <= 100; j++)
ans[i] += xs[j].size() - lowerBound(xs[j], points[i][0]);
return ans;
}
int lowerBound(List<Integer> xs, int x) {
int left = 0, right = xs.size();
while (left < right) {
var mid = (left + right) / 2;
if (xs.get(mid) >= x) right = mid;
else left = mid + 1;
}
return left;
}
}
class Solution:
# 按纵坐标排序
def countRectangles1(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 rectangles[i][1] >= y:
xs.append(rectangles[i][0])
i += 1
if start < i:
xs.sort() # 只有在 xs 插入了新元素时才排序
ans[id] = i - bisect_left(xs, x)
return ans
# 如果纵坐标范围也是10^9
def countRectangles2(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
from sortedcontainers import SortedList
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 rectangles[i][1] >= y:
xs.add(rectangles[i][0])
i += 1
ans[id] = i - xs.bisect_left(x)
return ans
# 按横坐标排序
def countRectangles3(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
rectangles.sort(key=lambda r: -r[0])
n = len(points)
ans = [0] * n
cnt = [0] * (max(y for _, y in rectangles) + 1)
i = 0
for (x, y), id in sorted(zip(points, range(n)), key=lambda x: -x[0][0]):
while i < len(rectangles) and rectangles[i][0] >= x:
cnt[rectangles[i][1]] += 1
i += 1
ans[id] = sum(cnt[y:])
return ans
# 按行统计+二分
def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
max_y = max(y for _, y in rectangles)
xs = [[] for _ in range(max_y + 1)]
for x, y in rectangles:
xs[y].append(x)
for x in xs:
x.sort()
return [sum(len(x) - bisect_left(x, px) for x in xs[py:]) for px, py in points]
