在二维平面上拟合线段

Question

我遇到了以下问题

给定一个大小为N x S的网格和m个与水平轴平行的线段（它们都是元组(x'，x''，y)），回答Q个在线查询的形式为(x'，x'')。这种查询的答案是最小的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。没有英文版的说明，并且测试用例以不同的方式呈现输入数据，所以请不要关注源代码。

- Atin

---

我不明白为什么查询(2,3)的答案会是2？(2,3,2)这样的一段可以放在哪里？ - yacc

由于一个片段的开始可以是另一个片段的结束，因此片段（2、3、2）没有任何问题，它会“扩展”片段（1、2、2），使它们看起来像一个单独的片段（1、3、2）（尽管该片段只是假设，初始棋盘不会改变）。 - Y N

也许您可以添加一些绘图来说明一个例子吗？ - yacc

问题描述中指出查询是在线的 - 看看公式 a = x_i + p，b = y_i + p以及p的更新方式。如果我们事先获得了所有查询，那么问题就容易多了。 - maniek

Answer 1

这里提供了一个O（N log N）的解决方案。

预备知识（教程请参见此处）：线段树，可持久化线段树。

第0部分。原始问题描述

我简要介绍一下原始问题陈述，因为后面我会用它的术语而不是抽象段落的术语说话。

有一列火车，有S个座位（S <= 10^5）。已知s_i座位从l_i时刻到r_i时刻被占用（不超过10^5的限制或旅客）。然后我们要回答10^5个查询，查询方式为“找到一个空闲的最低座位号，使其自l_i时刻到r_i时刻为空闲状态，否则报告不存在”。必须在线回答所有查询，也就是在看到下一个查询之前必须回答上一个查询。

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

第1部分。回答单个查询

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

但是，这可能不足以获得接受。我们需要O（log N）。回想一下，段树的每个节点存储相应范围内的最小值。我们从根开始。如果那里的最小值> = L，则没有可用的座位进行此类查询。否则，左子节点或右子节点中的最小值（或两者都有）均小于等于L。在第一种情况下，我们向左子节点下降，在第二种情况下，我们向右子节点下降，并重复直到到达叶子节点。该叶子节点将对应于具有last（S）<= L的最小座位。

第2部分。 解决问题

我们在座位上维护一个持久化的树，为每个座位存储最后的(S)，与前面的部分相同。按照左端点递增的顺序逐一处理初始乘客。对于乘客(s_i, l_i, r_i)，我们使用值r_i更新位置s_i处的段树。树是持久化的，因此我们将新副本存储在某个地方。

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

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

- Ivan Smirnov

Answer 2

说明：

输入：list<x',x'',Y>

查询输入：(X',X'')

输出：Ymin

限制条件：

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

Time: 1s
Memory: 256 Mb

---

答案：

你可以使用以下数据结构方法：

1. 暴力破解法：直接遍历列表并执行检查。

---

2. 排序：按Y [从小到大]对列表进行排序，然后遍历它。

注意：对大型列表进行排序将耗费时间。

Sort on Y
Ymin = -1                                            //Maintain Ymin
for i[0 : len(input)] :                              //Iterate through tuples
    if Ymin != -1 && Y(i-1) != Yi : return Ymin      // end case
    else if x' > X'' : Ymin = Yi                     //its on right of query tuple
    else if x'<X' && (x' + length <= X') : Ymin = Yi //on left of query tuple
    else next

---

3. 哈希表：使用Map<Y, list< tuple<x',length> > >来存储每个Y的行列表，并通过迭代它们来获取最小的Y。

注意：构建Map将需要额外的时间。

Iterate through list and build a Map 
Iterate through Map keys :
    Iterate through list of tuples, for each tuple :
        if x' > X'': Continue                            //its on right of query tuple
        else if x'<X' && (x' + length <= X') :  return Y //on left of query tuple
            else next Y

---

4. 矩阵：您可以使用1表示占用点，0表示空点来构建矩阵。

注意：构建矩阵需要额外的时间，并且遍历矩阵是耗时的，因此不太有用。

示例：

    0 1 1 1 0 0 
    1 1 0 1 0 0
    0 1 1 1 1 0

- akshay dhule