8

我遇到以下问题

给定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。该语句没有英文版本，并且测试用例以不同的方式呈现输入数据，所以不要介意源代码。

4

2 回答 2

3

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

Preliminaries（这里有一个很好的教程）：segment tree，persistent segment tree。

第 0 部分。原始问题陈述

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

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

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

第 1 部分。回答单个查询

让我们回答一个查询 [L, R]，假设在时间 R 之后没有被占用的位置。对于每个座位，我们维护它最后被占用的时间。最后叫它（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 部分中的算法来使用此段树来回答查询。

于 2017-11-13T22:37:36.767 回答
1

陈述 ：

输入 ：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. Hashmap：Map<Y, list< tuple<x',length> > >存储每行的列表Y并遍历它们以获得最少Y的。

注意：地图构建需要额外的时间。

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
于 2017-11-10T01:41:26.133 回答