algorithm - 您如何解决具有给定内存限制的给定场景？

Question

有N个菜园，编号为1到N，每第i个菜园都有Ci个胡萝卜。我们必须存储数组中每个可能的连续子序列的花园中胡萝卜总数的值。

现在我们必须对获得的数组进行排序并回答以下 Q 查询。在每个查询中，我们想知道上面获得的排序数组中从 L 到 R(包括两者)的值的总和。

示例测试用例

Input:
3 3    //First number is the total no. of gardens. Second is no. of queries
4 9 1  //No. of carrots in each of the gardens
1 6    // Query return sum from L to R.
2 4
3 3

Output:
51 23 9  // Respective Output for 3 queries.

解释

Gardens [1, 2, 3] has [4, 9, 1] carrots respectively.
All possible continuous gardens are { [1], [2], [3], [1, 2], [2, 3], [1, 2, 3] } .

Sum of carrots in each subgardens is {4, 9, 1, 13, 10, 14} 
Sorted array is {1, 4, 9, 10, 13, 14} .

Now Queries for 1 6 sum is 1+4+9+10+13+14 which is 51,
next 2 4 so 4+9+10 hence 23, and 3 3 which is 9.

现在我已经使用模拟/后缀和解决了这个问题，但是原始问题有很大的约束

1 ≤ No. of gardens ≤ 2*10^5
1 ≤ Carrots in a particular garden ≤ 100
1 ≤ Li ≤ Ri ≤ N(N+1)/2
1 ≤ No. of queries ≤ 20

现在，当我尝试为 N 大到 2*10^5 创建所有可能的连续子序列时。总数。我得到的连续子序列的大小约为 10^10，这太大而无法存储在数组中。

有什么可能的解决方法，我如何在不实际存储所有连续子序列总和的情况下回答查询？

Answer 1

这个怎么样？

假设 c[] = {c_1,c_2,..,c_n}，给定数组。而p[] = {c1, c1+c2,..,c1+...+cn}前缀数组。可视化将c的所有连续subs，分成n组(每组都是非递减数组):

1. { c1, c1+c2, .. , }

2. { c2, c2+c3, .. , c2+...+cn}...

   n. {cn}

请注意，使用前缀数组可以在恒定时间内计算上述所有元素。

让我们找到值 x，这样在我们选择的组中恰好有 l 个元素小于 x。 (x 的最大值为 c0+c1+..+cn)。为此，我们对 x 运行二分搜索，并计算给定 x 的 l 的值，我们在每个中运行二分搜索选定的组。所以我们将在每个组中拥有少于 x 的元素，我们需要对其进行总结。此操作的复杂度为 n*log(x)*log(x)。

现在我们得到范围 [l, r]。假设正好有 l-1 个元素小于 xl 和 r 个元素小于 xr。所以剩下的就是计算每组小于xr的元素之和，并减去每组小于xl的元素之和。使用二进制搜索和前缀和数组可以直接计算。

编辑

这里是使用上述方法的解决方案:https://ideone.com/2JTw0X

如有任何问题请追问。至于如何处理，如果确定范围的值不存在，我们需要计算偏移量，这很简单。例如在 1, 1, 1, 1, 1 的情况下。构建的组是:

{1,2,3,4,5}, {1,2,3,4},...,{1}。所以如果我们想找到值 x，s.t.恰好三个数字小于x，我们找到最小值x'，s.t。 f(x') >= 3。在本例中 x'=1。 f(1)=5 并且它严格大于 3，所以我们将在答案中加上 3(偏移量)并计算总和每个组中小于 x'-1 = 0 的元素的所有总和，即零。