2

你得到一个数组，比如 A[]，有 N 个元素，最初它们都等于负无穷大。

现在您被要求执行两种类型的查询（总共 M 个查询）：

键入 1。给定两个整数 a 和 d，您需要将数组 A[] 从索引 l 更新为索引 r。您需要做的是 - 对于每个包含某些值的索引 l+i（其中 0<=i<=rl），例如“val”，您需要使用最大值 a+i*d 更新该索引的值，并且val，即 A[l+i] = max(A[l+i], a+i*d)。

类型 2。给定一个整数“i”，您需要报告 A[i] 的值。

示例：让 N = 5 和 M = 4

initially A[] = {-inf, -inf, -inf, -inf, -inf}
query 1: l = 2, r = 4, a = 2, d = 3
new A[] = {-inf, 2, 5, 8, -inf}
query 2: i = 3
output = 5
query 3: l = 3, r = 5, a = 10, d = -6
new A[] = {-inf, 2, 10, 8, -2}
query 4: i = 5
output = -2

注意：N 和 M 的值可以大到 100000，所以我正在寻找比 O(N*M) 更好的算法。

谢谢。

4

1 回答 1

3

以这种方式思考问题：您正在管理一个分段线性函数集合 f i (x) = a i x + b i (l i <= x <= r i )服从以下操作：

  • 添加新功能
  • 找到迄今为止为特定x值定义的所有添加的函数的最大值

我看到两种可能的方法：

  1. 仅存储所有函数的最大值（“上壳”），它又是分段线性函数的集合，但定义区间不相交。更新：我最初认为这可以用一个简单的二叉搜索树来完成，但它并不那么简单，所以我会选择选项 2
  2. 遵循更标准的方法并使用x范围（“数组”）上的线段树，将线性函数集存储在其节点中。现在对于给定的x，您可以沿着树向上查找在该点定义了哪些线性函数，并使用标准凸包技巧在x处找到它们的最大值。复杂度：O(n + M * log n * log M)
于 2014-03-12T00:40:56.700 回答