范围内的最大总和元素
Maximum Sum Elements in Range
Given an array 'A' of size 'N' containing integers. You need to answer
'Q' queries of type [ L R X Y ]. In each of the query you need to
select at least 'X' elements and at most 'Y' elements from range 'L'
to 'R' of the array 'A' such that their sum is maximum.
Output the maximum sum achievable for each of the query.
Example :
N = 5
A = [ 1, 2, -1, -2, 3 ]
Q = [ [ 1, 3, 1, 2 ] , [ 3, 4, 1, 2 ] ]
Output : 3, -1
Expanation :
For query 1, we select integers 1 and 2 to get the sum 3. This is the
maximum sum achievable in the range index 1 to 3.
For query 2, we need to select at least 1 element so we select -1 to
get maximum sum -1.
Note :
The selected elements in the range L to R need not be consecutive. You can > select subsequence of integers to maximise the sum.
Constraints :
1<=N<=10^5
1<=Q<=10^5
-10^8 <= A[i] <= 10^8
1<=L<=R<=N
1<=X<=Y<=R-L+1
我试图想出一些方法，但找不到针对上述约束的任何算法。任何 help/hint 将不胜感激。
一种方法是通过拆分成 non-overlapping 个长度为 L 的数组（对于 L 等于 2 的不同次方）来预处理数字。
对每个数组进行排序，并计算每个数组的累加和。
然后对于每个查询，确定组合起来构成查询范围的数组，并使用二分法确定级别 T，这样如果取所有高于 T 的元素，我们最终得到合法数量的元素和最高总和。
将涉及 log(N) 个数组，每个二等分中的 log(N) 个步骤，因此这应该相当快。
(注意，如果我们的第一次评估表明取所有积极元素最终太多，我们需要通过二分法找到最低合法级别，而如果我们最终太少，我们需要找到最高合法级别通过二分法)
例子
假设我们有一个数组A = [ 1, -1, 2, -2, 3, -3, 4, 0 ]。
预处理会将其拆分为：
Two arrays of length 4: [ 1, -1, 2, -2], [ 3, -3, 4, 0 ]
Four arrays of length 2: [ 1, -1], [2, -2], [ 3, -3], [4, 0 ]
Eight arrays of length 1: [1], [-1], [2], [-2], [ 3], [-3], [4], [0 ]
然后通过查询 3 到 5，我们需要可以从数组 [-2] 和 [3,-3].
中形成的元素 [-2,3,-3]
假设我们现在要从至少 2 个元素中找到最大总和。
我们首先尝试取所有正元素，这只会产生 1 个元素，所以我们知道我们需要平分最高合法级别。
二分法可以通过尝试一些值来实现，例如
All elements >= 0 gives 1 element, so value is too high
All elements >= -4 gives 3 elements, so value is too low
All elements >= -2 gives 2 elements, so value is just right
Given an array 'A' of size 'N' containing integers. You need to answer 'Q' queries of type [ L R X Y ]. In each of the query you need to select at least 'X' elements and at most 'Y' elements from range 'L' to 'R' of the array 'A' such that their sum is maximum.
Output the maximum sum achievable for each of the query.
Example :
N = 5 A = [ 1, 2, -1, -2, 3 ] Q = [ [ 1, 3, 1, 2 ] , [ 3, 4, 1, 2 ] ]Output :
3, -1Expanation :
For query 1, we select integers 1 and 2 to get the sum 3. This is the maximum sum achievable in the range index 1 to 3.
For query 2, we need to select at least 1 element so we select -1 to get maximum sum -1.
Note :
The selected elements in the range L to R need not be consecutive. You can > select subsequence of integers to maximise the sum.
Constraints :
1<=N<=10^5 1<=Q<=10^5 -10^8 <= A[i] <= 10^8 1<=L<=R<=N 1<=X<=Y<=R-L+1
我试图想出一些方法，但找不到针对上述约束的任何算法。任何 help/hint 将不胜感激。
一种方法是通过拆分成 non-overlapping 个长度为 L 的数组（对于 L 等于 2 的不同次方）来预处理数字。
对每个数组进行排序，并计算每个数组的累加和。
然后对于每个查询，确定组合起来构成查询范围的数组，并使用二分法确定级别 T，这样如果取所有高于 T 的元素，我们最终得到合法数量的元素和最高总和。
将涉及 log(N) 个数组，每个二等分中的 log(N) 个步骤，因此这应该相当快。
(注意，如果我们的第一次评估表明取所有积极元素最终太多，我们需要通过二分法找到最低合法级别，而如果我们最终太少，我们需要找到最高合法级别通过二分法)
例子
假设我们有一个数组A = [ 1, -1, 2, -2, 3, -3, 4, 0 ]。
预处理会将其拆分为：
Two arrays of length 4: [ 1, -1, 2, -2], [ 3, -3, 4, 0 ]
Four arrays of length 2: [ 1, -1], [2, -2], [ 3, -3], [4, 0 ]
Eight arrays of length 1: [1], [-1], [2], [-2], [ 3], [-3], [4], [0 ]
然后通过查询 3 到 5，我们需要可以从数组 [-2] 和 [3,-3].
[-2,3,-3]
假设我们现在要从至少 2 个元素中找到最大总和。
我们首先尝试取所有正元素，这只会产生 1 个元素，所以我们知道我们需要平分最高合法级别。
二分法可以通过尝试一些值来实现，例如
All elements >= 0 gives 1 element, so value is too high
All elements >= -4 gives 3 elements, so value is too low
All elements >= -2 gives 2 elements, so value is just right