Wie lösen Sie das gegebene Szenario mit gegebenen Speicherbeschränkungen?

Question

Es gibt N Gärten nummeriert von 1 bis N in einer Reihe, jeder ith Garten hat Ci Karotten. Wir müssen den Wert der gesamten Karotten in Garten (n) jeder möglichen kontinuierlichen Untersequenz des Arrays speichern.

Nun müssen wir das erhaltene Array sortieren und folgende Q-Abfragen beantworten. In jeder Abfrage wollen wir die Summe der Werte von L bis R (beide inklusive) im oben erhaltenen sortierten Array kennen.

Beispieltestfall

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. 

Erklärung

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. 

nun dieses Problem, das ich Summe mit Simulation/Suffix gelöst haben, aber das ursprüngliche Problem

große Einschränkung hat

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 

Jetzt, wenn ich versuche, alle möglichen kontinuierlichen Teilfolge für N so groß wie 2 * 10^5 zu erstellen. der kontinuierlichen Untersequenz, die ich bekomme, ist ungefähr 10^10, was zu groß ist, um in einem Array gespeichert zu werden.

Was ist eine mögliche Problemumgehung dafür? Wie kann ich die Abfragen beantworten, ohne tatsächlich die Summe aller kontinuierlichen Subsequenz zu speichern?

Answer 1

Wie wäre es damit?

Angenommen c[] = {c_1,c_2,..,c_n}, Array gegeben. Und p[] = {c1, c1+c2,..,c1+...+cn} Präfix-Array. Visuell unterteilen alle kontinuierlichen subs von c, in n Gruppen (von denen jedes nicht abnehm Array ist):

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

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

   n. { cn }

anzumerken, dass unter Verwendung von Präfix-Array alle oben genannten Elemente können in konstanter Zeit berechnet werden.

Suchwert Lassen Sie uns x, so dass es genau l Elemente unter unseren ausgewählten Gruppen sind, die als x weniger sind. (Höchstwert von x ist c0+c1+..+cn). Um dies zu tun, führen wir binäre Suche auf x, und um den Wert l für eine gegebene x zu berechnen, führen wir binäre Suche in jeder der ausgewählten Gruppen. Also werden wir eine Anzahl von Elementen weniger als x in jeder der Gruppen haben, die wir zusammenfassen müssen. Die Komplexität dieses Vorgangs ist n*log(x)*log(x).

Jetzt haben wir den Bereich [l, r]. Nehmen wir an, es gibt genau l-1 Elemente weniger als xl und r Elemente weniger als xr. Es bleibt also übrig, die Summe der Elemente in jeder Gruppe unter xr zu berechnen und die entsprechende Summe in jeder Gruppe unter xl zu subtrahieren.Was mit Hilfe der binären Such- und Präfixsummenmatrix direkt berechnet werden kann.

EDIT

Dies ist die Lösung, die das Verfahren unter Verwendung der oben beschriebenen: https://ideone.com/2JTw0X

Pls fragen, ob irgendwelche Fragen haben. Für den Fall, wie zu behandeln ist, wenn der Wert, der den Bereich bestimmt, nicht existiert, müssen wir den Offset berechnen, was ziemlich einfach ist. Zum Beispiel im Fall von . Konstruierte Gruppen sind:

{1,2,3,4,5}, {1,2,3,4},...,{1}. Also, wenn wir Wert x finden möchten, s.t. genau drei Zahlen sind weniger als x, finden wir Mindestwert x', s.t. f(x') >= 3. In diesem Fall x'=1. f(1)=5 und es ist streng größer als 3, so fügen wir 3 (Offset) zu der Antwort hinzu und berechnen die Summe aller Summen von Elementen in jeder Gruppe, die kleiner als x'-1 = 0 sind, was Null ist.