关于成对的点和线段的任务
Task about pairs of points and segments
你能帮我解决问题吗？给定 N <= 10^5 对点，假设它们写在
数组 A、A[i][0] <= A[i][1]。此外，给定 M <= 10^5 对片段，第 i 对以 L_1[i], R_1[i], L_2[i], R_2[i] 形式给出。对于每一对段，我需要从数组 A 中找到对的数量，这样对于每一对 (A[z][0], A[z][1])，它应该是 L_1[i] <= A[z][0] <= R_1[i] <= L_2[i] <= A[z][1] <= R_2[i]。
我想这里我们可以使用扫描线算法，但我不知道如何适应时间和内存。我的想法适用于 N * M * log(N)。
如果你将 A[i] 映射到二维平面上的一个点 (A[i][0], A[i][1])，那么对于每个线段，基本上你只是在计算数量左下角为 (L_1[i], L_2[i]) 且右上角为 (R_1[i], R_2[一世]）。计算 2d 平面上的点是一个经典的问题，可以在 O(n logn) 中解决。以下是一些可能的实施方式：
注意矩形中的点数P(l,b,r,t)可以解释为P(0,0,r,t)-P(0,0,l-1,t)-P(0,0,r,b-1)+P(0,0,l-1,b-1)，所以问题可以简化为计算P(0,0,?,?)。如果我们在这个过程中维护一个基本上类似于扫描线算法的fenwick树，这可以很容易地完成。
为每个 x 坐标（时间 O(n logn)）构建一个持久线段树并计算线段的答案（时间 O(m logn)）。
构建一个 kd 树并在 O(sqrt(n)) 时间内回答每个查询。这效率不高，但当您想在线插入点和计算点数时可能会有用。
抱歉我的英语不好。欢迎指出我的错别字和错误。
你能帮我解决问题吗？给定 N <= 10^5 对点，假设它们写在
数组 A、A[i][0] <= A[i][1]。此外，给定 M <= 10^5 对片段，第 i 对以 L_1[i], R_1[i], L_2[i], R_2[i] 形式给出。对于每一对段，我需要从数组 A 中找到对的数量，这样对于每一对 (A[z][0], A[z][1])，它应该是 L_1[i] <= A[z][0] <= R_1[i] <= L_2[i] <= A[z][1] <= R_2[i]。
我想这里我们可以使用扫描线算法，但我不知道如何适应时间和内存。我的想法适用于 N * M * log(N)。
如果你将 A[i] 映射到二维平面上的一个点 (A[i][0], A[i][1])，那么对于每个线段，基本上你只是在计算数量左下角为 (L_1[i], L_2[i]) 且右上角为 (R_1[i], R_2[一世]）。计算 2d 平面上的点是一个经典的问题，可以在 O(n logn) 中解决。以下是一些可能的实施方式：
注意矩形中的点数
P(l,b,r,t)可以解释为P(0,0,r,t)-P(0,0,l-1,t)-P(0,0,r,b-1)+P(0,0,l-1,b-1)，所以问题可以简化为计算P(0,0,?,?)。如果我们在这个过程中维护一个基本上类似于扫描线算法的fenwick树，这可以很容易地完成。为每个 x 坐标（时间 O(n logn)）构建一个持久线段树并计算线段的答案（时间 O(m logn)）。
构建一个 kd 树并在 O(sqrt(n)) 时间内回答每个查询。这效率不高，但当您想在线插入点和计算点数时可能会有用。
抱歉我的英语不好。欢迎指出我的错别字和错误。