给定一个数组 A[]，我们需要找到一个具有最大大小且其最小元素 >= 1 的范围。我们还需要通过将其所有元素减 1 来更新此范围。
我的一个想法是保留一个线段树以进行高效更新。但是如何在 <= 对数时间内获得范围？
也许我们可以在这里使用二分查找。
谢谢
最佳答案
这是一个非常有趣的问题，我认为它可以使用线段树来解决。
这是我的想法(我希望它运作得足够快):
对于每个段，我们需要存储 4 个信息:
- 数字 < 1 的最左边索引
- 数字 < 1 的最右边索引
- 此段的最大大小(存储为范围 a 和 b)
- 惰性标志(真/假)
当我们想要查询最大尺寸时，我们可以进行递归调用来计算最终答案。 假设我们的方法是 calcAnswer(left,right)。
resA = calcAnswer(左, 中);
resB = calcAnswer(mid+1,right);
最大尺寸将为 max(resA.max_size, resB.max_size, combine(resA.right_index,resB.left_index))。
如果数组A[]中的元素个数很少(N<=50000)，我们可以使用Mo's Algorithm .
关于algorithm - 在比线性时间更快的时间内找到满足属性的范围，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42168443/