0

Given an array A[] we need to find a range which has the maximum size and its minimum element is >= 1. We also need to update this range by decreasing all its elements by 1.

One idea I got is to keep a segment tree for efficient updates. But how do I get the range in <= logarithmic time?

Maybe we can use binary search here.

Thanks

4

1 回答 1

1

这是一个非常有趣的问题，我认为可以使用 Segment Tree 来解决。

这是我的想法（我希望它工作得足够快）：

对于每个段，我们需要存储 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。

于 2017-02-10T21:18:37.613 回答