您如何解决具有给定内存限制的给定场景？
How do you solve the given scenario with given memory constraints?
一排有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，这太大而无法存储在数组中。
有什么可能的解决方法，我如何在不实际存储所有连续子序列总和的情况下回答查询？
这个怎么样？
假设c[] = {c_1,c_2,..,c_n}，给定数组。和 p[] = {c1, c1+c2,..,c1+...+cn} 前缀数组。可视化将c的所有连续subs分成n组（每组为非递减数组）：
{ c1, c1+c2, .. , }{ 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(offset) 添加到答案中并计算每个组中小于 [= 的所有元素和的总和44=]，这是零。
一排有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，这太大而无法存储在数组中。
有什么可能的解决方法，我如何在不实际存储所有连续子序列总和的情况下回答查询？
这个怎么样？
假设c[] = {c_1,c_2,..,c_n}，给定数组。和 p[] = {c1, c1+c2,..,c1+...+cn} 前缀数组。可视化将c的所有连续subs分成n组（每组为非递减数组）：
{ c1, c1+c2, .. , }{ 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(offset) 添加到答案中并计算每个组中小于 [= 的所有元素和的总和44=]，这是零。