在二维平面中拟合线段
Fitting a segment in a two-dimensional plane
我遇到了以下问题
Given N x S grid and m segments parallel to the horizontal axis (all of them are tuples (x', x'', y)), answer Q online queries of form (x', x''). The answer to such a query is the smallest y (if there is one) such that we can place a segment (x', x'', y). All segments are non-overlapping yet beginning of one segment can be the ending of another i.e. segments (x', x'', y) and (x'', x''', y) are allowed. Being able to place a segment means there could exist a segment (x', x'', y) that wouldn't violate stated rules, segment isn't actually placed(board with initial segments isn't modified) but we only state there could be one.
约束条件
1 ≤ Q, S, m ≤ 10^5
1 ≤ N ≤ 10^9
Time: 1s
Memory: 256 Mb
下面是 link 中的示例。输入段为 (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 找到。没有英文版本的语句可用，测试用例以不同的方式呈现输入数据，所以不要介意来源。
声明：
输入：list<x',x'',Y>
查询输入：(X',X'')
输出：Ymin
约束：
1 ≤ Q, S, m ≤ 10^5
1 ≤ N ≤ 10^9
Time: 1s
Memory: 256 Mb
答案：
你可以使用的数据结构方法：
1. Brute force : 直接遍历列表并执行检查。
2。 Sort ：根据 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. Matrix : 可以构建矩阵，1为占据点，0为空。
注意： 构建矩阵需要额外的时间，并且通过矩阵进行迭代非常耗时，因此没有用。
示例：
0 1 1 1 0 0
1 1 0 1 0 0
0 1 1 1 1 0
这是一个 O(N log N) 时间的解决方案。
预备知识（有很好的教程here）：线段树，持久线段树。
第 0 部分。原始问题陈述
我简要描述了最初的问题陈述，稍后我将用它的术语而不是抽象的片段来讲述。
有一列火车有 S 个座位 (S <= 10^5)。已知座位 s_i 从时间 l_i 到时间 r_i 被占用（不超过 10^5 这样的限制，或乘客）。然后我们必须回答 10^5 个 "find the lowest number of a seat with is free from time l_i to time r_i or say if there is none" 类型的查询。所有查询都必须在线回答，即您必须先回答上一个问题才能看到下一个问题。
在整个文本中，我用 N 表示座位数、乘客数和查询数，假设它们是相同的数量级。如果需要，您可以进行更准确的分析。
第 1 部分。回答单个查询
让我们回答一个查询 [L, R] 假设在时间 R 之后没有被占用的位置。对于每个座位，我们维护它最后一次被占用的时间。最后调用它（S）。现在查询的答案是最小 S，使得 last(S) <= L。如果我们在座位上构建一个线段树，那么我们将能够在 O(log^2 N) 时间内回答这个查询：二分查找S 的值，检查段 [0, S] 上的范围最小值是否最多为 L.
但是，获得录取可能还不够。我们需要 O(log N)。回想一下，线段树的每个节点都存储相应范围内的最小值。我们从根开始。如果最小值 >= L 则没有可用的座位可用于此类查询。否则，左侧 child 或右侧 child 中的最小值 <= L（或两者均有）。在第一种情况下，我们向左 child 下降，在第二种情况下 - 向右下降，并重复直到我们到达一片叶子。此叶子将对应于 last(S) <= L.
的最小座位
第 2 部分. 解决问题
我们在座位上维护一棵持久树，为每个座位存储 last(S)（与上一部分相同）。让我们按左端点递增的顺序逐一处理初始乘客。对于乘客 (s_i、l_i、r_i)，我们将位置 s_i 处的线段树更新为值 r_i。树是持久的，所以我们将新副本存储在某个地方。
要回答查询 [L, R]，请找到最新版本的线段树，以便更新发生在 R 之前。如果对版本进行二分查找，则需要 O(log N) 时间。
在线段树的版本中，只考虑左端点 < R 的乘客（甚至更多，正是这样的乘客）。所以我们可以使用第 1 部分中的算法来使用这个线段树回答查询。
我遇到了以下问题
Given N x S grid and m segments parallel to the horizontal axis (all of them are tuples (x', x'', y)), answer Q online queries of form (x', x''). The answer to such a query is the smallest y (if there is one) such that we can place a segment (x', x'', y). All segments are non-overlapping yet beginning of one segment can be the ending of another i.e. segments (x', x'', y) and (x'', x''', y) are allowed. Being able to place a segment means there could exist a segment (x', x'', y) that wouldn't violate stated rules, segment isn't actually placed(board with initial segments isn't modified) but we only state there could be one.
约束条件
1 ≤ Q, S, m ≤ 10^5
1 ≤ N ≤ 10^9
Time: 1s
Memory: 256 Mb
下面是 link 中的示例。输入段为 (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 找到。没有英文版本的语句可用，测试用例以不同的方式呈现输入数据，所以不要介意来源。
声明：
输入：list<x',x'',Y>
查询输入：(X',X'')
输出：Ymin
约束：
1 ≤ Q, S, m ≤ 10^5
1 ≤ N ≤ 10^9
Time: 1s
Memory: 256 Mb
答案：
你可以使用的数据结构方法：
1. Brute force : 直接遍历列表并执行检查。
2。 Sort ：根据 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. Matrix : 可以构建矩阵，1为占据点，0为空。
注意： 构建矩阵需要额外的时间，并且通过矩阵进行迭代非常耗时，因此没有用。
示例：
0 1 1 1 0 0
1 1 0 1 0 0
0 1 1 1 1 0
这是一个 O(N log N) 时间的解决方案。
预备知识（有很好的教程here）：线段树，持久线段树。
第 0 部分。原始问题陈述
我简要描述了最初的问题陈述，稍后我将用它的术语而不是抽象的片段来讲述。
有一列火车有 S 个座位 (S <= 10^5)。已知座位 s_i 从时间 l_i 到时间 r_i 被占用（不超过 10^5 这样的限制，或乘客）。然后我们必须回答 10^5 个 "find the lowest number of a seat with is free from time l_i to time r_i or say if there is none" 类型的查询。所有查询都必须在线回答，即您必须先回答上一个问题才能看到下一个问题。
在整个文本中，我用 N 表示座位数、乘客数和查询数，假设它们是相同的数量级。如果需要，您可以进行更准确的分析。
第 1 部分。回答单个查询
让我们回答一个查询 [L, R] 假设在时间 R 之后没有被占用的位置。对于每个座位，我们维护它最后一次被占用的时间。最后调用它（S）。现在查询的答案是最小 S，使得 last(S) <= L。如果我们在座位上构建一个线段树，那么我们将能够在 O(log^2 N) 时间内回答这个查询：二分查找S 的值，检查段 [0, S] 上的范围最小值是否最多为 L.
但是，获得录取可能还不够。我们需要 O(log N)。回想一下，线段树的每个节点都存储相应范围内的最小值。我们从根开始。如果最小值 >= L 则没有可用的座位可用于此类查询。否则，左侧 child 或右侧 child 中的最小值 <= L（或两者均有）。在第一种情况下，我们向左 child 下降，在第二种情况下 - 向右下降，并重复直到我们到达一片叶子。此叶子将对应于 last(S) <= L.
的最小座位第 2 部分. 解决问题
我们在座位上维护一棵持久树，为每个座位存储 last(S)（与上一部分相同）。让我们按左端点递增的顺序逐一处理初始乘客。对于乘客 (s_i、l_i、r_i)，我们将位置 s_i 处的线段树更新为值 r_i。树是持久的，所以我们将新副本存储在某个地方。
要回答查询 [L, R]，请找到最新版本的线段树，以便更新发生在 R 之前。如果对版本进行二分查找，则需要 O(log N) 时间。
在线段树的版本中，只考虑左端点 < R 的乘客（甚至更多，正是这样的乘客）。所以我们可以使用第 1 部分中的算法来使用这个线段树回答查询。