在二维平面中拟合分段

Question

我遇到了以下问题的麻烦

给定N x S网格和m个平行于水平轴的段(所有这些都是元组(x',x'',y)),回答形式(x',x'')的Q在线查询.这种查询的答案是最小的y(如果有的话),这样我们就可以放置一个段(x',x'',y).所有段都是非重叠的,但是一个段的开头可以是另一个段的结尾,即允许段(x',x',y)和(x'',x'',y).能够放置一个段意味着可能存在一个段(x',x'',y)不会违反规定的规则,段实际上并未放置(具有初始段的板未被修改)但我们只说明可能有一个.

约束

1 ? Q, S, m ? 10^5
1 ? N ? 10^9

Time: 1s
Memory: 256 Mb

以下是以下链接中的示例.输入段是(2,5,1),(1,2,2),(4,5,2),(2,3,3),(3,4,3).
回答查询

1)(1,2)→1

2)(2,3)→2

3)(3,4)→2

4)(4,5)→3

5)(1,3)→不能放置一个段

第三个查询的可视化答案(蓝色部分):

我不太明白如何处理这个问题.它应该用持久的分段树来解决,但我仍然无法想出一些东西.

请问你能帮帮我吗.

这不是我的功课.源问题可以在http://informatics.mccme.ru/mod/statements/view3.php?chapterid=111614找到.可用的语句没有英文版本,测试用例以不同的方式显示输入数据,所以不要介意源.

Answer 1

这是一个 O(N log N) 时间解决方案。

\n\n

预备知识（这里有一个很好的教程有一个很好的教程）：线段树，持久线段树。

\n\n

第 0 部分：原始问题陈述

\n\n

我简要描述了最初的问题陈述，稍后我将用它的术语而不是抽象片段来说话。

\n\n

有一趟火车有 S 个座位（S <= 10^5）。已知座位 s_i 从时间 l_i 到时间 r_i 被占用（不超过 10^5 个此类约束或乘客）。然后我们必须回答 10^5 个这样的查询：“找到从时间 l_i 到时间 r_i 空闲的座位的最低编号，或者说是否没有”。所有查询都必须在线回答，也就是说，您必须先回答上一个查询，然后才能看到下一个查询。

\n\n

在整个文本中，我用 N 表示座位数、乘客数和查询数，假设它们的数量级相同。如果需要，您可以进行更准确的分析。

\n\n

第 1 部分：回答单个查询

\n\n

让我们回答一个查询 [L, R] ，假设在时间 R 之后没有被占用的位置。对于每个座位，我们维护它最后被占用的时间。称之为最后（S）。现在，查询的答案是最小 S，使得 last(S) <= L。如果我们在座位上构建线段树，那么我们将能够在 O(log^2 N) 时间内回答此查询：二分搜索S 的值，检查段 [0, S] 上的范围最小值是否至多为 L。

\n\n

然而，这可能还不足以获得接受。我们需要 O(log N)。回想一下，线段树的每个节点都存储相应范围内的最小值。我们从根源开始。如果最小值 >= L，则此类查询没有可用座位。否则，左子节点或右子节点的最小值 <= L（或两者）。在第一种情况下，我们下降到左边的孩子，在右边的第二个 \xe2\x80\x93 中，重复直到到达叶子。该叶子将对应于last(S) <= L 的最小座位。

\n\n

第 2 部分. 解决问题

\n\n

我们在座位上维护一棵持久树，存储每个座位的最后一个（S）（与前一部分相同）。让我们按照左端点升序逐一处理初始乘客。对于乘客 (s_i, l_i, r_i)，我们用值 r_i 更新位置 s_i 处的线段树。该树是持久的，因此我们将新副本存储在某处。

\n\n

要回答查询 [L, R]，请查找线段树的最新版本，使得更新发生在 R 之前。如果对版本进行二分搜索，则需要 O(log N) 时间。

\n\n

在线段树的版本中，仅考虑左端点 < R 的乘客（甚至更确切地说，正是这样的乘客）。因此，我们可以使用第 1 部分中的算法来回答使用此线段树的查询。

\n