如何解決給定內存限制的給定場景？

Question

有N個花園連續編號爲1到N，每個花園都有慈胡蘿蔔。 我們必須在陣列的每個可能的連續子序列的花園中存儲總胡蘿蔔的值。

現在我們已經得到的數組進行排序，並回答以下的問答查詢。在每個查詢中，我們想知道上面獲得的排序數組中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，成n基（其中的每一個是非遞減陣列）：

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

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

   ñ。 { cn }

注意，使用前綴陣列中的所有的上述元件可在恆定的時間來計算。

讓我們找到價值x，這樣有我們選定的組之間究竟l元素都小於x。 （最大值x是c0+c1+..+cn）。要做到這一點，我們就x運行二進制搜索，以及計算的l對於給定x價值，我們在每個運行中所選組的二進制搜索。因此，我們將在每個組中包含少於x的元素數量，這是我們需要總結的。此操作的複雜性爲n*log(x)*log(x)。

現在我們給定的範圍[l, r]。假設只有l-1元素小於xl和r元素小於xr。那麼剩下的就是計算每個組中小於xr的元素總和，並且減去每個組中小於xl的對應總和。使用二分查找和前綴和數組計算簡單。

EDIT

下面是使用如上所述的方法將溶液：https://ideone.com/2JTw0X

PLS詢問是否有任何問題。至於如何處理的情況，如果確定範圍的值不存在，我們需要計算偏移量，這很簡單。例如在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，這是零。