你能帮我解决问题吗？给N <= 10^5定点对，假设它们写在数组A, 中A[i][0] <= A[i][1]。此外，给定M <= 10^5的段对，i第 -th 对以形式给出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).
问问题
62 次
1 回答
0
如果将 A[i] 映射到 2d 平面上的一个点 (A[i][0], A[i][1])，那么对于每个段，基本上你只是在计算矩形内的点数其左下角为 (L_1[i], L_2[i])，右上角为 (R_1[i], R_2[i])。计算二维平面上的点是一个经典问题，可以在 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-tree 并在 O(sqrt(n)) 时间内回答每个查询。这效率不高，但当您想要在线插入点和计算点时可能很有用。
对不起我的英语不好。随时指出我的错别字和错误。
于 2021-07-03T14:16:56.610 回答