有N个花园，连续编号为1到N，每个花园都有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的所有连续子划分为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(偏移量(添加到答案中，并计算每个组中小于 x'-1 = 0 的所有元素总和的总和，即零。