給定一個包含整數的大小為“N”的陣列“A”。您需要回答 [LRXY] 型別的“Q”查詢。在每個查詢中，您需要從陣列“A”的“L”到“R”范圍內選擇至少“X”個元素和最多“Y”個元素，以使它們的總和最大。
輸出每個查詢可實作的最大總和。
例子 ：
N = 5 A = [ 1, 2, -1, -2, 3 ] Q = [ [ 1, 3, 1, 2 ] , [ 3, 4, 1, 2 ] ]輸出：
3, -1擴展：
對于查詢 1，我們選擇整數 1 和 2 得到總和 3。這是在范圍索引 1 到 3 中可實作的最大總和。
對于查詢 2，我們需要選擇至少 1 個元素，因此我們選擇 -1 以獲得最大總和 -1。
筆記 ：
L 到 R 范圍內的選定元素不必是連續的。您可以 > 選擇整數子序列以最大化總和。
約束：
1<=N<=10^5 1<=Q<=10^5 -10^8 <= A[i] <= 10^8 1<=L<=R<=N 1<=X<=Y<=R-L 1
我試圖想出一些方法，但找不到上述約束的任何演算法。任何幫助/提示將不勝感激。
uj5u.com熱心網友回復：
一種方法是通過拆分為長度為 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 ]
[-2,3,-3]然后通過查詢 3 到 5，我們想要我們可以從陣列[-2]和中形成的元素[3,-3]。
假設我們現在想從至少 2 個元素中找到最大和。
我們首先嘗試取所有積極的元素，這只會產生 1 個元素，所以我們知道我們需要平分最高的法律級別。
二等分可以通過嘗試一些值來作業，例如
All elements >= 0 gives 1, so too high
All elements >= -4 gives 4, so too low
All elements >= -2 gives 2, so just right
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/479496.html
下一篇：PythonDFS嵌套字典