不同商店的数量

Number of distinct shops

提问人：joshua 提问时间：10/6/2023 更新时间：10/6/2023 访问量：49

问：

一个人是一条数线的原点，其范围从负无穷大到正无穷大。 给定一个由字符 L 和 R 组成的字符串，L 表示该人从 x 到 x-1，R 表示他从 x 到 x+1。 给定一些具有范围 [u，v] 的查询。如果忽略从 u 到 v 的索引，找出该人访问了多少个唯一数字。

例如 考虑从 1 开始的索引 字符串 - RRRRRR 查询 - [[1,4]，[2,4]] 输出 - 3， 4 解释 - [1,4] 忽略从 1 到 4 的索引，字符串保持 RR。人去 +1 和 +2，他已经在 0。所以房子总数 = 3

查询应立即得到答复。我想到了简单的蛮力方法，但那将是 O（Q*N） 和 1<= Q，N <= 10^5。我也想过用前缀 sum 做一些事情，但没有得到完整的想法。谁能帮我想出一个有效的算法？我自己可以做的编码

数组 算法 数学

评论

0赞 user3386109 10/6/2023
给定一个查询，您需要五条信息。1） 以 结束的序列向左的最大偏移。2） 以 结束的序列向右的最大偏移。3） 以 .4） 从 . 开始的序列向左的最大偏移。5） 从 . 开始的序列向右的最大偏移。所有这些信息都可以在 O（N） 时间内计算，然后每个查询都可以在 O（1） 时间内处理。[a,b]a-1a-1a-1b+1b+1

答：

0赞 Dave 10/6/2023 #1
  1. 预处理：在O（n）时间内，找到访问的最左边和最右边的位置，将它们称为“开始”和“结束”。
  2. 给定查询 [a，b]，将其转换为 [a'， b']，其中 a' = max（a， start） 和 b' = min（b， end）。
  3. 返回 （结束 - 开始） - （b' - a'）。

每个查询的所有工作都是 O（1），预处理为 O（n）。

例如，考虑从 1 开始的索引字符串 - RRRRRR 查询 - [[1,4]，[2,4]]

start = 0
end = 6
q1: a=1, b=4. Since these are in-range, a'=1 and b'=4. (6-0) - (4-1) = 6-3 = 3.
q2: a=2, b=4. Same reasoning: (6-0) - (3-1) = 6-2 = 4.

上一个：CS50 拼字游戏 - 我自己的实验室方法

下一个：以编程方式查找有限序列中的数字