The sequence in the repository is generated by
$$S_{n+1}\equiv S_n^2 \pmod{50515093},\qquad S_0=290797,$$
and the working array starts at \(S_1=629527\). For the first \(N=2\cdot 10^9\) terms we must evaluate
$$M(N)=\sum_{1\le l\le r\le N}\min(S_l,S_{l+1},\ldots,S_r).$$
A direct scan over all subarrays is hopeless, and even the standard linear-time subarray-minimum technique cannot be run on \(2\cdot 10^9\) explicit values. The solution used in the C++, Python, and Java files therefore compresses the sequence to one period and then counts how often each position of that period owns a minimum.
The map \(x\mapsto x^2 \bmod 50515093\) is deterministic on a finite state space, so once a value repeats, the future repeats as well. The implementation starts from \(S_1\), keeps generating values until \(S_1\) appears again, and obtains one full cycle
$$a_1,a_2,\ldots,a_p,\qquad p=6308948.$$
Hence the infinite sequence relevant to the problem is the periodic extension
$$b_x=a_{((x-1)\bmod p)+1}\qquad (x\ge 1).$$
Write the target length as
$$N=qp+r,\qquad 0\le r<p.$$
Then period index \(i\) appears
$$\operatorname{occ}_i=q+\mathbf{1}_{i\le r}$$
times inside the first \(N\) terms.
For a fixed absolute position \(x\), the classical contribution method counts how many subarrays have \(b_x\) as their representative minimum. Equal values require a tie-breaking rule. The code uses a strict comparison on the left and a non-strict comparison on the right, so ties are assigned to the rightmost occurrence of the minimum.
For a period index \(i\), with cyclic indexing modulo \(p\), define
$$d_R(i)=\min\{k\ge 1: a_{i+k}\le a_i\},$$
and define \(d_L(i)\) as the smallest \(k\ge 1\) with \(a_{i-k}<a_i\) if such a value exists within one full period to the left; otherwise set \(d_L(i)=0\).
The quantity \(d_R(i)\) is always at most \(p\), because the same value reappears one full period later. For \(d_L(i)\), looking back only one period is enough: if no strictly smaller value occurs there, periodicity implies that no strictly smaller value exists anywhere earlier.
The implementations scan two consecutive copies of the period. A right-to-left monotone stack produces the next position with value \(\le a_i\), which gives \(d_R(i)\). A left-to-right monotone stack with the opposite strictness produces the previous position with value \(<a_i\), which gives \(d_L(i)\).
This is the usual subarray-minimum ownership trick, but adapted to a cyclic array. Two copies are sufficient because no relevant comparison can jump farther than one period.
The \(t\)-th occurrence of period index \(i\) in the prefix of length \(N\) sits at
$$x_{i,t}=(t-1)p+i,\qquad 1\le t\le \operatorname{occ}_i.$$
If \(L_{i,t}\) is the number of admissible left endpoints and \(R_{i,t}\) is the number of admissible right endpoints for subarrays owned by that occurrence, then its contribution is
$$a_i\,L_{i,t}\,R_{i,t}.$$
Every occurrence except the last one has the full right span \(d_R(i)\). Only the last occurrence may be cut by the end of the prefix. Its remaining tail length is
$$\operatorname{tail}_i=\begin{cases} r-i+1, & i\le r,\\ p+r-i+1, & i>r, \end{cases}$$
so the actual right factor on the last copy is
$$R_i^{\text{last}}=\min(d_R(i),\operatorname{tail}_i).$$
If \(d_L(i)=0\), then no strictly smaller value exists anywhere to the left, so the left span is simply the absolute position itself:
$$L_{i,t}=x_{i,t}=(t-1)p+i.$$
When \(\operatorname{occ}_i=1\), this gives
$$C_i=a_i\cdot i\cdot R_i^{\text{last}}.$$
When \(\operatorname{occ}_i\ge 2\), the first \(\operatorname{occ}_i-1\) copies use the full right span \(d_R(i)\), so the code sums an arithmetic progression:
$$\sum_{t=1}^{\operatorname{occ}_i-1}\big((t-1)p+i\big) =(\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}.$$
Therefore
$$C_i=a_i\left[ d_R(i)\left((\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}\right) +\big((\operatorname{occ}_i-1)p+i\big)R_i^{\text{last}} \right].$$
If \(d_L(i)>0\), the first copy may be truncated on the left, but every later copy has the fixed left span \(d_L(i)\). Let
$$L_i^{\text{first}}=\min(d_L(i),i).$$
Then, for \(\operatorname{occ}_i=1\),
$$C_i=a_i\,L_i^{\text{first}}\,R_i^{\text{last}},$$
and for \(\operatorname{occ}_i\ge 2\),
$$C_i=a_i\left[L_i^{\text{first}}d_R(i)+(\operatorname{occ}_i-2)d_L(i)d_R(i)+d_L(i)R_i^{\text{last}}\right].$$
The required value is the sum over one period:
$$\boxed{M(N)=\sum_{i=1}^{p} C_i.}$$
The C++ solution separates the work into build_period_sequence(), build_spans(), and sum_subarray_min_prefix(). The Python and Java versions mirror the same formulas and case split. The C++ file also checks the key intermediate facts used by the derivation:
$$p=6308948,\qquad M(10)=432256955,\qquad M(10000)=3264567774119.$$
Those checkpoints are important because they validate both the period construction and the strict/non-strict ownership convention before the final \(N=2\cdot 10^9\) computation is performed.
Building one period takes \(O(p)\) time. Each monotone-stack pass is \(O(p)\), because every position is pushed and popped at most once. The final aggregation over all \(p\) period indices is again \(O(p)\). Thus the full algorithm runs in \(O(p)\) time and \(O(p)\) memory, with \(p=6308948\), while the huge input \(N\) only appears through the two integers \(q\) and \(r\).
Die im Repository verwendete Folge entsteht durch
$$S_{n+1}\equiv S_n^2 \pmod{50515093},\qquad S_0=290797,$$
wobei das Arbeitsarray bei \(S_1=629527\) beginnt. Für die ersten \(N=2\cdot 10^9\) Terme ist
$$M(N)=\sum_{1\le l\le r\le N}\min(S_l,S_{l+1},\ldots,S_r)$$
zu berechnen. Eine naive Betrachtung aller Teilintervalle ist unmöglich, daher reduziert die Implementierung die Folge zuerst auf eine Periode und zählt dann, wie oft jede Position dieser Periode das Minimum eines Intervalls „besitzt“.
Die Abbildung \(x\mapsto x^2 \bmod 50515093\) ist deterministisch auf einer endlichen Zustandsmenge. Sobald ein Wert erneut auftritt, wiederholt sich die Zukunft periodisch. Das Programm startet bei \(S_1\), erzeugt Werte bis \(S_1\) wieder erscheint, und erhält so genau eine volle Periode
$$a_1,a_2,\ldots,a_p,\qquad p=6308948.$$
Damit ist die relevante unendliche Folge die periodische Fortsetzung
$$b_x=a_{((x-1)\bmod p)+1}\qquad (x\ge 1).$$
Schreibe die Zielgröße als
$$N=qp+r,\qquad 0\le r<p.$$
Dann erscheint der Periodenindex \(i\) in den ersten \(N\) Termen genau
$$\operatorname{occ}_i=q+\mathbf{1}_{i\le r}$$
Mal.
Für eine absolute Position \(x\) zählt die übliche Beitragsmethode, in wie vielen Teilintervallen \(b_x\) das repräsentative Minimum ist. Bei gleichen Werten braucht man eine feste Tie-Break-Regel. Der Code benutzt links einen strikten Vergleich und rechts einen nicht-strikten Vergleich; dadurch gehören Gleichstände dem rechtesten Auftreten des Minimums.
Für einen Periodenindex \(i\), mit zyklischer Indizierung modulo \(p\), definiert man
$$d_R(i)=\min\{k\ge 1: a_{i+k}\le a_i\},$$
und \(d_L(i)\) ist das kleinste \(k\ge 1\) mit \(a_{i-k}<a_i\), falls ein solcher Wert innerhalb einer ganzen Periode links existiert; sonst setzt man \(d_L(i)=0\).
Die Größe \(d_R(i)\) ist immer höchstens \(p\), weil derselbe Wert spätestens eine Periode später erneut vorkommt. Für \(d_L(i)\) genügt der Blick um genau eine Periode zurück: Gibt es dort keinen strikt kleineren Wert, dann gibt es wegen der Periodizität auch weiter links keinen.
Die Implementierungen betrachten zwei aufeinanderfolgende Kopien der Periode. Ein rechts-nach-links-Scan mit monotonem Stack liefert die nächste Position mit Wert \(\le a_i\) und damit \(d_R(i)\). Ein links-nach-rechts-Scan mit umgekehrter Striktheit liefert die vorherige Position mit Wert \(<a_i\) und damit \(d_L(i)\).
Das ist dieselbe Idee wie bei der Standardaufgabe „Summe der Teilarray-Minima“, nur auf ein zyklisches Array angepasst. Zwei Kopien genügen, weil keine relevante Vergleichsbeziehung weiter als eine Periode springen kann.
Das \(t\)-te Auftreten des Periodenindex \(i\) im Präfix der Länge \(N\) liegt an der absoluten Position
$$x_{i,t}=(t-1)p+i,\qquad 1\le t\le \operatorname{occ}_i.$$
Seien \(L_{i,t}\) die zulässigen linken Endpunkte und \(R_{i,t}\) die zulässigen rechten Endpunkte der von diesem Auftreten besessenen Intervalle. Dann ist sein Beitrag
$$a_i\,L_{i,t}\,R_{i,t}.$$
Alle Auftreten außer dem letzten haben rechts die volle Spannweite \(d_R(i)\). Nur das letzte Auftreten kann durch das Ende des Präfixes abgeschnitten werden. Seine Restlänge ist
$$\operatorname{tail}_i=\begin{cases} r-i+1, & i\le r,\\ p+r-i+1, & i>r, \end{cases}$$
also ist der tatsächliche rechte Faktor auf der letzten Kopie
$$R_i^{\text{last}}=\min(d_R(i),\operatorname{tail}_i).$$
Falls \(d_L(i)=0\), existiert links nirgendwo ein strikt kleinerer Wert. Dann ist die linke Spannweite einfach die absolute Position:
$$L_{i,t}=x_{i,t}=(t-1)p+i.$$
Für \(\operatorname{occ}_i=1\) folgt sofort
$$C_i=a_i\cdot i\cdot R_i^{\text{last}}.$$
Für \(\operatorname{occ}_i\ge 2\) benutzen die ersten \(\operatorname{occ}_i-1\) Kopien die volle rechte Spannweite \(d_R(i)\). Daher summiert der Code eine arithmetische Folge:
$$\sum_{t=1}^{\operatorname{occ}_i-1}\big((t-1)p+i\big) =(\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}.$$
Damit ergibt sich
$$C_i=a_i\left[ d_R(i)\left((\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}\right) +\big((\operatorname{occ}_i-1)p+i\big)R_i^{\text{last}} \right].$$
Falls \(d_L(i)>0\), kann nur die erste Kopie links gekappt sein; jede spätere Kopie hat die feste linke Spannweite \(d_L(i)\). Setze
$$L_i^{\text{first}}=\min(d_L(i),i).$$
Dann gilt für \(\operatorname{occ}_i=1\)
$$C_i=a_i\,L_i^{\text{first}}\,R_i^{\text{last}},$$
und für \(\operatorname{occ}_i\ge 2\)
$$C_i=a_i\left[L_i^{\text{first}}d_R(i)+(\operatorname{occ}_i-2)d_L(i)d_R(i)+d_L(i)R_i^{\text{last}}\right].$$
Die gesuchte Summe ist also
$$\boxed{M(N)=\sum_{i=1}^{p} C_i.}$$
Die C++-Lösung zerlegt die Aufgabe in build_period_sequence(), build_spans() und sum_subarray_min_prefix(). Die Python- und Java-Dateien folgen denselben Formeln und demselben Fallsplit. Zusätzlich überprüft die C++-Datei die entscheidenden Zwischenresultate der Herleitung:
$$p=6308948,\qquad M(10)=432256955,\qquad M(10000)=3264567774119.$$
Diese Kontrollwerte sind wichtig, weil sie sowohl die Periodenkonstruktion als auch die strikt/nicht-strikt gewählte Besitzregel validieren, bevor das endgültige \(N=2\cdot 10^9\) berechnet wird.
Der Aufbau einer Periode kostet \(O(p)\) Zeit. Jeder monotone-Stack-Durchlauf ist ebenfalls \(O(p)\), weil jede Position höchstens einmal auf den Stack gelegt und wieder entfernt wird. Die abschließende Summation über alle \(p\) Periodenpositionen ist erneut \(O(p)\). Insgesamt läuft das Verfahren also in \(O(p)\) Zeit und \(O(p)\) Speicher, mit \(p=6308948\); die riesige Eingabe \(N\) geht nur über die zwei Zahlen \(q\) und \(r\) ein.
Depodaki çözümün kullandığı dizi
$$S_{n+1}\equiv S_n^2 \pmod{50515093},\qquad S_0=290797,$$
özyinelemesiyle üretilir ve çalışma dizisi \(S_1=629527\) ile başlar. İlk \(N=2\cdot 10^9\) terim için hesaplanması istenen toplam
$$M(N)=\sum_{1\le l\le r\le N}\min(S_l,S_{l+1},\ldots,S_r)$$
şeklindedir. Tüm alt dizileri doğrudan saymak imkansızdır. Bu yüzden çözüm önce diziyi tek bir periyoda indirger, sonra da bu periyottaki her konumun kaç alt dizide minimumun sahibi olduğunu hesaplar.
\(x\mapsto x^2 \bmod 50515093\) dönüşümü sonlu bir durum uzayında deterministiktir. Bir değer tekrar görüldüğünde bundan sonraki tüm değerler de periyodik olarak tekrar eder. Kod \(S_1\)'den başlar, \(S_1\) yeniden görünene kadar üretim yapar ve tek bir tam çevrim elde eder:
$$a_1,a_2,\ldots,a_p,\qquad p=6308948.$$
Böylece problem için gerekli sonsuz dizi şu periyodik uzatmadır:
$$b_x=a_{((x-1)\bmod p)+1}\qquad (x\ge 1).$$
Hedef uzunluğu
$$N=qp+r,\qquad 0\le r<p$$
şeklinde yazalım. O zaman periyottaki \(i\) konumu, ilk \(N\) terimde
$$\operatorname{occ}_i=q+\mathbf{1}_{i\le r}$$
kez görünür.
Sabit bir mutlak konum \(x\) için klasik katkı yöntemi, \(b_x\) değerinin kaç alt dizide temsilci minimum olduğunu sayar. Eşit değerler varsa bir bağ bozma kuralı gerekir. Kod solda sıkı, sağda gevşek karşılaştırma kullanır; bu yüzden eşit minimumlar arasında sahiplik en sağdaki kopyaya verilir.
Periyottaki \(i\) konumu için, indekslerin \(p\)'ye göre döndüğünü kabul ederek,
$$d_R(i)=\min\{k\ge 1: a_{i+k}\le a_i\}$$
tanımlanır. Ayrıca \(d_L(i)\), solda bir tam periyot içinde \(a_{i-k}<a_i\) koşulunu sağlayan en küçük \(k\ge 1\) değeridir; böyle bir değer yoksa \(d_L(i)=0\) alınır.
\(d_R(i)\) her zaman en fazla \(p\)'dir; çünkü aynı değer bir periyot sonra tekrar görünür. \(d_L(i)\) için yalnızca bir periyot geriye bakmak yeterlidir: orada daha küçük bir değer yoksa, periyodiklik nedeniyle daha eski kopyalarda da yoktur.
Uygulamalar periyodun arka arkaya yazılmış iki kopyasını tarar. Sağdan sola giden monotonik bir stack, değeri \(\le a_i\) olan ilk sağ konumu bulur ve \(d_R(i)\)'yi verir. Soldan sağa giden, ters sıkılık kullanan ikinci stack ise değeri \(<a_i\) olan ilk sol konumu bulur ve \(d_L(i)\)'yi verir.
Bu yöntem, standart alt dizi minimumları algoritmasının da kullandığı sahiplik fikridir; burada yalnızca döngüsel diziye uyarlanmıştır. İlgili karşılaştırmalar bir tam periyottan daha uzağa sıçrayamayacağı için iki kopya yeterlidir.
Uzunluğu \(N\) olan ön ekte, periyot indeks \(i\)'nin \(t\)-inci görünümü şu mutlak konumdadır:
$$x_{i,t}=(t-1)p+i,\qquad 1\le t\le \operatorname{occ}_i.$$
\(L_{i,t}\) bu görünüm için geçerli sol uç sayısı, \(R_{i,t}\) ise geçerli sağ uç sayısı olsun. Bu durumda katkı
$$a_i\,L_{i,t}\,R_{i,t}$$
olur. Son görünüm dışındaki tüm kopyalarda sağ span tam olarak \(d_R(i)\)'dir. Yalnızca son görünüm, ön ekin sonu tarafından kesilebilir. Kalan kuyruk uzunluğu
$$\operatorname{tail}_i=\begin{cases} r-i+1, & i\le r,\\ p+r-i+1, & i>r \end{cases}$$
olduğundan son kopyadaki gerçek sağ faktör
$$R_i^{\text{last}}=\min(d_R(i),\operatorname{tail}_i)$$
şeklindedir.
Eğer \(d_L(i)=0\) ise solda hiçbir yerde daha küçük bir değer yoktur. Bu durumda sol span doğrudan mutlak konuma eşittir:
$$L_{i,t}=x_{i,t}=(t-1)p+i.$$
\(\operatorname{occ}_i=1\) için katkı
$$C_i=a_i\cdot i\cdot R_i^{\text{last}}$$
olur. \(\operatorname{occ}_i\ge 2\) olduğunda ilk \(\operatorname{occ}_i-1\) kopya tam sağ span \(d_R(i)\)'yi kullanır ve kod bir aritmetik dizi toplar:
$$\sum_{t=1}^{\operatorname{occ}_i-1}\big((t-1)p+i\big) =(\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}.$$
Dolayısıyla
$$C_i=a_i\left[ d_R(i)\left((\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}\right) +\big((\operatorname{occ}_i-1)p+i\big)R_i^{\text{last}} \right].$$
Eğer \(d_L(i)>0\) ise yalnızca ilk kopya solda kırpılabilir; sonraki tüm kopyalarda sol span sabit olarak \(d_L(i)\) olur. Şunu tanımlayalım:
$$L_i^{\text{first}}=\min(d_L(i),i).$$
O zaman \(\operatorname{occ}_i=1\) için
$$C_i=a_i\,L_i^{\text{first}}\,R_i^{\text{last}},$$
ve \(\operatorname{occ}_i\ge 2\) için
$$C_i=a_i\left[L_i^{\text{first}}d_R(i)+(\operatorname{occ}_i-2)d_L(i)d_R(i)+d_L(i)R_i^{\text{last}}\right].$$
Sonuçta aranılan değer
$$\boxed{M(N)=\sum_{i=1}^{p} C_i}$$
olur.
C++ çözümü işi build_period_sequence(), build_spans() ve sum_subarray_min_prefix() fonksiyonlarına ayırır. Python ve Java sürümleri de aynı formülleri ve aynı durum ayrımını uygular. C++ dosyası ayrıca türetimin dayandığı temel ara sonuçları doğrular:
$$p=6308948,\qquad M(10)=432256955,\qquad M(10000)=3264567774119.$$
Bu kontrol noktaları önemlidir; çünkü hem periyot kurulumunu hem de sıkı/gevşek sahiplik kuralını, asıl \(N=2\cdot 10^9\) hesabından önce test eder.
Bir periyodu üretmek \(O(p)\) zaman alır. Her monotonik stack geçişi de \(O(p)\)'dir; çünkü her konum en fazla bir kez stack'e girer ve çıkar. Tüm \(p\) periyot konumu üzerinden yapılan son toplama yine \(O(p)\)'dir. Bu nedenle tüm algoritma \(O(p)\) zamanda ve \(O(p)\) bellekte çalışır. Burada \(p=6308948\) olup, devasa \(N\) yalnızca \(q\) ve \(r\) sayıları üzerinden işleme girer.
La secuencia usada por las soluciones del repositorio se genera mediante
$$S_{n+1}\equiv S_n^2 \pmod{50515093},\qquad S_0=290797,$$
y el arreglo de trabajo empieza en \(S_1=629527\). Para los primeros \(N=2\cdot 10^9\) términos hay que calcular
$$M(N)=\sum_{1\le l\le r\le N}\min(S_l,S_{l+1},\ldots,S_r).$$
Enumerar todos los subarreglos es imposible, y tampoco se puede aplicar una versión lineal directa sobre \(2\cdot 10^9\) valores explícitos. La idea real de la implementación es comprimir la sucesión a un solo período y contar cuántas veces cada posición de ese período es la dueña del mínimo.
La transformación \(x\mapsto x^2 \bmod 50515093\) es determinista sobre un conjunto finito de estados. En cuanto un valor reaparece, todo el futuro se vuelve periódico. El programa arranca en \(S_1\), sigue generando términos hasta que reaparece \(S_1\), y así obtiene un ciclo completo
$$a_1,a_2,\ldots,a_p,\qquad p=6308948.$$
La sucesión infinita relevante para el problema es entonces la extensión periódica
$$b_x=a_{((x-1)\bmod p)+1}\qquad (x\ge 1).$$
Escribimos la longitud objetivo como
$$N=qp+r,\qquad 0\le r<p.$$
Por lo tanto, el índice periódico \(i\) aparece
$$\operatorname{occ}_i=q+\mathbf{1}_{i\le r}$$
veces dentro de los primeros \(N\) términos.
Para una posición absoluta \(x\), el método clásico de contribuciones cuenta en cuántos subarreglos \(b_x\) actúa como mínimo representativo. Cuando hay valores iguales se necesita una convención fija. El código usa comparación estricta a la izquierda y no estricta a la derecha; así, entre mínimos iguales, la propiedad se asigna a la copia más a la derecha.
Para un índice de período \(i\), leyendo los subíndices de manera cíclica módulo \(p\), se define
$$d_R(i)=\min\{k\ge 1: a_{i+k}\le a_i\},$$
y \(d_L(i)\) es el menor \(k\ge 1\) tal que \(a_{i-k}<a_i\), si existe dentro de un período completo hacia la izquierda; en caso contrario se toma \(d_L(i)=0\).
Siempre se cumple \(d_R(i)\le p\), porque el mismo valor reaparece exactamente una vuelta después. Para \(d_L(i)\), mirar un solo período hacia atrás basta: si allí no hay ningún valor estrictamente menor, entonces por periodicidad tampoco lo habrá más atrás.
Las implementaciones recorren dos copias consecutivas del período. Un stack monótono de derecha a izquierda encuentra la siguiente posición con valor \(\le a_i\), lo que produce \(d_R(i)\). Otro stack, de izquierda a derecha y con la desigualdad opuesta, encuentra la posición previa con valor \(<a_i\), lo que produce \(d_L(i)\).
Es exactamente la idea estándar de “sum of subarray minimums”, pero adaptada a un arreglo cíclico. Dos copias bastan porque ninguna comparación relevante puede saltar más de un período completo.
La \(t\)-ésima aparición del índice periódico \(i\) dentro del prefijo de longitud \(N\) está en la posición absoluta
$$x_{i,t}=(t-1)p+i,\qquad 1\le t\le \operatorname{occ}_i.$$
Si \(L_{i,t}\) es el número de extremos izquierdos válidos y \(R_{i,t}\) el número de extremos derechos válidos para los subarreglos poseídos por esa copia, entonces su aporte es
$$a_i\,L_{i,t}\,R_{i,t}.$$
Todas las apariciones salvo la última conservan el span derecho completo \(d_R(i)\). Solo la última puede quedar recortada por el final del prefijo. La longitud restante es
$$\operatorname{tail}_i=\begin{cases} r-i+1, & i\le r,\\ p+r-i+1, & i>r, \end{cases}$$
y por ello el factor derecho real de la última copia es
$$R_i^{\text{last}}=\min(d_R(i),\operatorname{tail}_i).$$
Si \(d_L(i)=0\), no existe ningún valor estrictamente menor a la izquierda. En ese caso el span izquierdo coincide con la posición absoluta:
$$L_{i,t}=x_{i,t}=(t-1)p+i.$$
Cuando \(\operatorname{occ}_i=1\), el aporte es
$$C_i=a_i\cdot i\cdot R_i^{\text{last}}.$$
Cuando \(\operatorname{occ}_i\ge 2\), las primeras \(\operatorname{occ}_i-1\) copias usan el span derecho completo \(d_R(i)\), y el código suma una progresión aritmética:
$$\sum_{t=1}^{\operatorname{occ}_i-1}\big((t-1)p+i\big) =(\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}.$$
Por tanto,
$$C_i=a_i\left[ d_R(i)\left((\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}\right) +\big((\operatorname{occ}_i-1)p+i\big)R_i^{\text{last}} \right].$$
Si \(d_L(i)>0\), solo la primera copia puede estar truncada por la izquierda; todas las demás tienen span izquierdo fijo \(d_L(i)\). Definimos
$$L_i^{\text{first}}=\min(d_L(i),i).$$
Entonces, para \(\operatorname{occ}_i=1\),
$$C_i=a_i\,L_i^{\text{first}}\,R_i^{\text{last}},$$
y para \(\operatorname{occ}_i\ge 2\),
$$C_i=a_i\left[L_i^{\text{first}}d_R(i)+(\operatorname{occ}_i-2)d_L(i)d_R(i)+d_L(i)R_i^{\text{last}}\right].$$
El valor buscado es
$$\boxed{M(N)=\sum_{i=1}^{p} C_i.}$$
La versión en C++ divide el trabajo en build_period_sequence(), build_spans() y sum_subarray_min_prefix(). Las versiones en Python y Java siguen exactamente las mismas fórmulas y el mismo desdoblamiento por casos. El archivo C++ además verifica los puntos de control que sostienen toda la derivación:
$$p=6308948,\qquad M(10)=432256955,\qquad M(10000)=3264567774119.$$
Esas comprobaciones son importantes porque validan tanto la construcción del período como la convención estricta/no estricta antes de evaluar el objetivo final \(N=2\cdot 10^9\).
Construir un período cuesta \(O(p)\) tiempo. Cada pasada con stack monótono también es \(O(p)\), ya que cada posición se apila y desapila como mucho una vez. La agregación final sobre los \(p\) índices periódicos vuelve a ser \(O(p)\). En consecuencia, todo el algoritmo funciona en \(O(p)\) tiempo y \(O(p)\) memoria, con \(p=6308948\); el enorme \(N\) solo entra a través de los dos enteros \(q\) y \(r\).
仓库中的解法使用如下递推生成序列：
$$S_{n+1}\equiv S_n^2 \pmod{50515093},\qquad S_0=290797,$$
实际参与计算的数组从 \(S_1=629527\) 开始。我们要求前 \(N=2\cdot 10^9\) 项所有连续子段最小值之和：
$$M(N)=\sum_{1\le l\le r\le N}\min(S_l,S_{l+1},\ldots,S_r).$$
直接枚举所有子段完全不可行。即使知道“子数组最小值求和”的线性技巧，也不能真的在 \(2\cdot 10^9\) 个显式元素上运行。仓库中的实现因此先把序列压缩成一个周期，再统计该周期中每个位置作为最小值代表时的贡献次数。
映射 \(x\mapsto x^2 \bmod 50515093\) 在有限状态空间上是确定性的，所以一旦某个值再次出现，后面的序列就会循环。程序从 \(S_1\) 出发，一直生成到 \(S_1\) 再次出现，从而得到一个完整周期
$$a_1,a_2,\ldots,a_p,\qquad p=6308948.$$
于是与题目相关的无限序列可以写成周期延拓
$$b_x=a_{((x-1)\bmod p)+1}\qquad (x\ge 1).$$
把目标长度写成
$$N=qp+r,\qquad 0\le r<p.$$
那么周期中的第 \(i\) 个位置在前 \(N\) 项中会出现
$$\operatorname{occ}_i=q+\mathbf{1}_{i\le r}$$
次。
对某个绝对位置 \(x\) 来说，经典贡献法会统计有多少个子段把 \(b_x\) 当作代表性的最小值。若存在相等元素，就必须规定平局如何处理。代码在左边使用严格比较、右边使用非严格比较，因此当最小值重复出现时，所有权归给最右边的那个副本。
对周期位置 \(i\)，按模 \(p\) 的循环下标定义
$$d_R(i)=\min\{k\ge 1: a_{i+k}\le a_i\},$$
而 \(d_L(i)\) 定义为满足 \(a_{i-k}<a_i\) 的最小 \(k\ge 1\)，前提是这样的值在左边一个完整周期内存在；如果不存在，就记 \(d_L(i)=0\)。
\(d_R(i)\) 一定不超过 \(p\)，因为同一个值在一整周期之后会再次出现。对 \(d_L(i)\) 只需向左看一个周期：如果这一段里都没有更小值，那么由于整体是周期性的，更早的位置也不会突然出现更小值。
实现中把一个周期复制两份首尾相接。自右向左的单调栈找到右边第一个满足 \(\le a_i\) 的位置，从而得到 \(d_R(i)\)。自左向右、使用相反严格性的第二个单调栈找到左边第一个满足 \(<a_i\) 的位置，从而得到 \(d_L(i)\)。
这和标准的“子数组最小值求和”算法本质相同，只是这里要处理循环数组。之所以两份拷贝就够，是因为任何相关比较都不可能跨越超过一个完整周期。
在长度为 \(N\) 的前缀中，周期位置 \(i\) 的第 \(t\) 次出现位于绝对位置
$$x_{i,t}=(t-1)p+i,\qquad 1\le t\le \operatorname{occ}_i.$$
设 \(L_{i,t}\) 是这个副本可选的左端点个数，\(R_{i,t}\) 是可选的右端点个数，那么它对总和的贡献就是
$$a_i\,L_{i,t}\,R_{i,t}.$$
除了最后一次出现以外，其余副本的右侧跨度都是完整的 \(d_R(i)\)。只有最后一次出现可能被前缀末端截断。其剩余尾长为
$$\operatorname{tail}_i=\begin{cases} r-i+1, & i\le r,\\ p+r-i+1, & i>r, \end{cases}$$
因此最后一个副本真正的右侧因子是
$$R_i^{\text{last}}=\min(d_R(i),\operatorname{tail}_i).$$
如果 \(d_L(i)=0\)，说明左边根本不存在严格更小的值，于是左跨度就等于绝对位置本身：
$$L_{i,t}=x_{i,t}=(t-1)p+i.$$
当 \(\operatorname{occ}_i=1\) 时，贡献直接是
$$C_i=a_i\cdot i\cdot R_i^{\text{last}}.$$
当 \(\operatorname{occ}_i\ge 2\) 时，前 \(\operatorname{occ}_i-1\) 个副本都能使用完整右跨度 \(d_R(i)\)，所以代码求的是一个等差和：
$$\sum_{t=1}^{\operatorname{occ}_i-1}\big((t-1)p+i\big) =(\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}.$$
于是
$$C_i=a_i\left[ d_R(i)\left((\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}\right) +\big((\operatorname{occ}_i-1)p+i\big)R_i^{\text{last}} \right].$$
如果 \(d_L(i)>0\)，只有第一个副本可能在左侧被截断，后面的副本左跨度都固定为 \(d_L(i)\)。记
$$L_i^{\text{first}}=\min(d_L(i),i).$$
那么当 \(\operatorname{occ}_i=1\) 时，
$$C_i=a_i\,L_i^{\text{first}}\,R_i^{\text{last}},$$
而当 \(\operatorname{occ}_i\ge 2\) 时，
$$C_i=a_i\left[L_i^{\text{first}}d_R(i)+(\operatorname{occ}_i-2)d_L(i)d_R(i)+d_L(i)R_i^{\text{last}}\right].$$
最终答案就是
$$\boxed{M(N)=\sum_{i=1}^{p} C_i.}$$
C++ 版本把流程拆成 build_period_sequence()、build_spans() 和 sum_subarray_min_prefix() 三部分。Python 与 Java 版本采用完全相同的公式和分支结构。C++ 文件还显式检查了推导中最关键的中间结论：
$$p=6308948,\qquad M(10)=432256955,\qquad M(10000)=3264567774119.$$
这些检查很重要，因为它们先验证了周期构造和左右严格性约定，再去计算真正的目标 \(N=2\cdot 10^9\)。
构造一个周期需要 \(O(p)\) 时间。两次单调栈扫描也都是 \(O(p)\)，因为每个位置最多入栈、出栈一次。最后对全部 \(p\) 个周期位置做汇总仍然是 \(O(p)\)。因此整体算法时间复杂度为 \(O(p)\)，空间复杂度也为 \(O(p)\)，其中 \(p=6308948\)。超大的 \(N\) 只通过两个整数 \(q\) 和 \(r\) 进入公式。
В репозитории используется последовательность, заданная рекуррентно:
$$S_{n+1}\equiv S_n^2 \pmod{50515093},\qquad S_0=290797,$$
причём рабочий массив начинается с \(S_1=629527\). Нужно вычислить сумму минимумов по всем непрерывным подпоследовательностям первых \(N=2\cdot 10^9\) членов:
$$M(N)=\sum_{1\le l\le r\le N}\min(S_l,S_{l+1},\ldots,S_r).$$
Полный перебор всех отрезков невозможен. Поэтому решение сначала сжимает последовательность до одного периода, а затем считает, сколько раз каждая позиция этого периода является владельцем минимума.
Отображение \(x\mapsto x^2 \bmod 50515093\) детерминировано на конечном множестве состояний. Как только значение повторяется, вся дальнейшая последовательность становится периодической. Программа стартует с \(S_1\), генерирует значения до нового появления \(S_1\) и получает полный цикл
$$a_1,a_2,\ldots,a_p,\qquad p=6308948.$$
Следовательно, нужная бесконечная последовательность есть периодическое продолжение
$$b_x=a_{((x-1)\bmod p)+1}\qquad (x\ge 1).$$
Представим длину префикса в виде
$$N=qp+r,\qquad 0\le r<p.$$
Тогда индекс периода \(i\) встречается в первых \(N\) членах
$$\operatorname{occ}_i=q+\mathbf{1}_{i\le r}$$
раз.
Для фиксированной абсолютной позиции \(x\) стандартный метод вкладов считает, во скольких подотрезках значение \(b_x\) выступает представителем минимума. При равных значениях нужна договорённость о разрыве ничьих. Код использует строгую проверку слева и нестрогую справа, поэтому при равных минимумах владелец выбирается как самое правое вхождение.
Для позиции периода \(i\), при циклической индексации по модулю \(p\), вводится
$$d_R(i)=\min\{k\ge 1: a_{i+k}\le a_i\},$$
а \(d_L(i)\) равно наименьшему \(k\ge 1\), для которого \(a_{i-k}<a_i\), если такое значение существует в пределах одного полного периода слева; иначе полагаем \(d_L(i)=0\).
Всегда \(d_R(i)\le p\), потому что то же самое значение встретится снова через один период. Для \(d_L(i)\) достаточно смотреть только на один период назад: если там нет строго меньшего значения, то по периодичности его не будет и ещё левее.
Реализация просматривает две подряд записанные копии периода. Монотонный стек справа налево находит ближайшую позицию со значением \(\le a_i\), то есть вычисляет \(d_R(i)\). Второй монотонный стек, идущий слева направо с противоположной строгостью, находит ближайшую позицию со значением \(<a_i\), то есть вычисляет \(d_L(i)\).
Это тот же приём, что и в обычной задаче о сумме минимумов подмассивов, только адаптированный к циклическому массиву. Двух копий достаточно, поскольку никакое важное сравнение не может перескочить дальше одного полного периода.
\(t\)-е появление индекса периода \(i\) в префиксе длины \(N\) имеет абсолютную позицию
$$x_{i,t}=(t-1)p+i,\qquad 1\le t\le \operatorname{occ}_i.$$
Пусть \(L_{i,t}\) обозначает число допустимых левых концов, а \(R_{i,t}\) число допустимых правых концов для подотрезков, которыми владеет это появление. Тогда его вклад равен
$$a_i\,L_{i,t}\,R_{i,t}.$$
У всех появлений, кроме последнего, справа доступен полный span \(d_R(i)\). Только последнее появление может быть обрезано концом префикса. Оставшаяся длина хвоста равна
$$\operatorname{tail}_i=\begin{cases} r-i+1, & i\le r,\\ p+r-i+1, & i>r, \end{cases}$$
поэтому фактический правый множитель у последней копии есть
$$R_i^{\text{last}}=\min(d_R(i),\operatorname{tail}_i).$$
Если \(d_L(i)=0\), то слева нигде нет строго меньшего значения. Значит, левый span просто совпадает с абсолютной позицией:
$$L_{i,t}=x_{i,t}=(t-1)p+i.$$
При \(\operatorname{occ}_i=1\) получаем
$$C_i=a_i\cdot i\cdot R_i^{\text{last}}.$$
Если \(\operatorname{occ}_i\ge 2\), то первые \(\operatorname{occ}_i-1\) копий используют полный правый span \(d_R(i)\), и код суммирует арифметическую прогрессию:
$$\sum_{t=1}^{\operatorname{occ}_i-1}\big((t-1)p+i\big) =(\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}.$$
Следовательно,
$$C_i=a_i\left[ d_R(i)\left((\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}\right) +\big((\operatorname{occ}_i-1)p+i\big)R_i^{\text{last}} \right].$$
Если \(d_L(i)>0\), то только первая копия может быть усечена слева; у всех следующих левый span фиксирован и равен \(d_L(i)\). Обозначим
$$L_i^{\text{first}}=\min(d_L(i),i).$$
Тогда при \(\operatorname{occ}_i=1\)
$$C_i=a_i\,L_i^{\text{first}}\,R_i^{\text{last}},$$
а при \(\operatorname{occ}_i\ge 2\)
$$C_i=a_i\left[L_i^{\text{first}}d_R(i)+(\operatorname{occ}_i-2)d_L(i)d_R(i)+d_L(i)R_i^{\text{last}}\right].$$
Искомая величина равна
$$\boxed{M(N)=\sum_{i=1}^{p} C_i.}$$
В версии на C++ решение разделено на три части: build_period_sequence(), build_spans() и sum_subarray_min_prefix(). Реализации на Python и Java повторяют те же формулы и тот же разбор случаев. В файле C++ дополнительно проверяются ключевые промежуточные факты:
$$p=6308948,\qquad M(10)=432256955,\qquad M(10000)=3264567774119.$$
Эти контрольные значения важны, потому что подтверждают и правильность построения периода, и выбранное строгое/нестрогое правило владения ещё до финального вычисления для \(N=2\cdot 10^9\).
Построение одного периода занимает \(O(p)\) времени. Каждый проход монотонного стека также работает за \(O(p)\), потому что каждая позиция добавляется в стек и удаляется из него не более одного раза. Финальное суммирование по всем \(p\) позициям периода снова требует \(O(p)\). Итак, весь алгоритм имеет сложность \(O(p)\) по времени и \(O(p)\) по памяти, где \(p=6308948\), а огромное значение \(N\) участвует только через два числа \(q\) и \(r\).
المتتالية المستخدمة في حلول المستودع تُولد بالعلاقة
$$S_{n+1}\equiv S_n^2 \pmod{50515093},\qquad S_0=290797,$$
ويبدأ المصفوف الفعلي من \(S_1=629527\). المطلوب هو حساب مجموع القيم الدنيا لكل المقاطع المتصلة ضمن أول \(N=2\cdot 10^9\) حدًا:
$$M(N)=\sum_{1\le l\le r\le N}\min(S_l,S_{l+1},\ldots,S_r).$$
العد المباشر لكل المقاطع مستحيل عمليًا. لذلك تعتمد الحلول المحلية على ضغط المتتالية إلى دورة واحدة ثم حساب عدد المقاطع التي تكون فيها كل موضعة من هذه الدورة هي المالكة للقيمة الدنيا.
الدالة \(x\mapsto x^2 \bmod 50515093\) حتمية على فضاء حالات منتهٍ، ولذلك فإن تكرار قيمة واحدة يعني أن المستقبل كله سيصبح دوريًا. يبدأ البرنامج من \(S_1\)، ويولد القيم حتى تظهر \(S_1\) مرة أخرى، وبهذا نحصل على دورة كاملة
$$a_1,a_2,\ldots,a_p,\qquad p=6308948.$$
وعليه فإن المتتالية اللانهائية المتعلقة بالمسألة هي الامتداد الدوري
$$b_x=a_{((x-1)\bmod p)+1}\qquad (x\ge 1).$$
نكتب طول البادئة المطلوبة على الصورة
$$N=qp+r,\qquad 0\le r<p.$$
وعندئذ يظهر الموضع الدوري \(i\) داخل أول \(N\) حدًا بعدد مرات يساوي
$$\operatorname{occ}_i=q+\mathbf{1}_{i\le r}.$$
بالنسبة إلى موضع مطلق \(x\)، فإن طريقة المساهمات التقليدية تعد عدد المقاطع التي يكون فيها \(b_x\) هو الممثل المعتمد للقيمة الدنيا. وعند وجود قيم متساوية نحتاج إلى قاعدة كسر تعادل ثابتة. الكود يستخدم مقارنة صارمة في الجهة اليسرى وغير صارمة في الجهة اليمنى، ولذلك تُسند الملكية إلى النسخة اليمنى عند تساوي القيم الدنيا.
للموضع الدوري \(i\)، مع قراءة الفهارس دوريًا بترديد \(p\)، نعرف
$$d_R(i)=\min\{k\ge 1: a_{i+k}\le a_i\},$$
أما \(d_L(i)\) فهو أصغر \(k\ge 1\) يحقق \(a_{i-k}<a_i\) إذا وُجد مثل هذا الموضع داخل دورة كاملة إلى اليسار؛ وإذا لم يوجد فنأخذ \(d_L(i)=0\).
لدينا دائمًا \(d_R(i)\le p\) لأن القيمة نفسها تعود بعد دورة كاملة. وبالنسبة إلى \(d_L(i)\)، يكفي النظر دورة واحدة إلى الخلف: إذا لم نجد فيها قيمة أصغر strictly، فلن تظهر قيمة أصغر في أي نسخة أقدم بسبب الدورية.
التنفيذ يمر على نسختين متتاليتين من الدورة. مسح أحادي الرتابة من اليمين إلى اليسار يعثر على أول موضع إلى اليمين يحقق \(\le a_i\)، ومن ثم يعطي \(d_R(i)\). ومسح آخر من اليسار إلى اليمين مع عكس الصرامة يعثر على أول موضع سابق يحقق \(<a_i\)، ومن ثم يعطي \(d_L(i)\).
هذه هي الفكرة نفسها المستخدمة في خوارزمية مجموع القيم الدنيا للمقاطع، لكنها هنا معدلة لتناسب مصفوفة دورية. وتكفي نسختان فقط لأن أي مقارنة مؤثرة لا يمكن أن تتجاوز دورة كاملة واحدة.
الظهور رقم \(t\) للموضع الدوري \(i\) داخل البادئة ذات الطول \(N\) يقع في الموضع المطلق
$$x_{i,t}=(t-1)p+i,\qquad 1\le t\le \operatorname{occ}_i.$$
إذا رمزنا بعدد النهايات اليسرى الصالحة بـ \(L_{i,t}\)، وعدد النهايات اليمنى الصالحة بـ \(R_{i,t}\)، فإن مساهمة هذه النسخة تساوي
$$a_i\,L_{i,t}\,R_{i,t}.$$
كل النسخ ما عدا الأخيرة تمتلك الامتداد الأيمن الكامل \(d_R(i)\). النسخة الأخيرة فقط قد تُقصَر بسبب نهاية البادئة. وطول الذيل المتبقي لها هو
$$\operatorname{tail}_i=\begin{cases} r-i+1, & i\le r,\\ p+r-i+1, & i>r, \end{cases}$$
ومن ثم فإن العامل الأيمن الحقيقي للنسخة الأخيرة هو
$$R_i^{\text{last}}=\min(d_R(i),\operatorname{tail}_i).$$
إذا كان \(d_L(i)=0\)، فهذا يعني أنه لا توجد إلى اليسار أي قيمة أصغر strictly، ولذلك يصبح الامتداد الأيسر مساويًا للموضع المطلق نفسه:
$$L_{i,t}=x_{i,t}=(t-1)p+i.$$
وعندما يكون \(\operatorname{occ}_i=1\) نحصل مباشرة على
$$C_i=a_i\cdot i\cdot R_i^{\text{last}}.$$
أما إذا كان \(\operatorname{occ}_i\ge 2\)، فإن أول \(\operatorname{occ}_i-1\) نسخ تستعمل الامتداد الأيمن الكامل \(d_R(i)\)، ولذلك يجمع الكود متتالية حسابية:
$$\sum_{t=1}^{\operatorname{occ}_i-1}\big((t-1)p+i\big) =(\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}.$$
ومن ثم
$$C_i=a_i\left[ d_R(i)\left((\operatorname{occ}_i-1)i+p\frac{(\operatorname{occ}_i-2)(\operatorname{occ}_i-1)}{2}\right) +\big((\operatorname{occ}_i-1)p+i\big)R_i^{\text{last}} \right].$$
أما إذا كان \(d_L(i)>0\)، فإن النسخة الأولى وحدها قد تُقصَر من اليسار، بينما تمتلك النسخ اللاحقة امتدادًا أيسر ثابتًا مقداره \(d_L(i)\). لنعرّف
$$L_i^{\text{first}}=\min(d_L(i),i).$$
حينئذ، إذا كان \(\operatorname{occ}_i=1\)، فإن
$$C_i=a_i\,L_i^{\text{first}}\,R_i^{\text{last}},$$
وإذا كان \(\operatorname{occ}_i\ge 2\)، فإن
$$C_i=a_i\left[L_i^{\text{first}}d_R(i)+(\operatorname{occ}_i-2)d_L(i)d_R(i)+d_L(i)R_i^{\text{last}}\right].$$
وبذلك تكون القيمة المطلوبة هي
$$\boxed{M(N)=\sum_{i=1}^{p} C_i.}$$
نسخة C++ تقسم العمل إلى الدوال build_period_sequence() وbuild_spans() وsum_subarray_min_prefix(). أما نسختا Python وJava فتتبنيان الصيغ نفسها والتفريع نفسه بين الحالات. كذلك يحتوي ملف C++ على نقاط تحقق أساسية تؤكد صحة المشتقات الرياضية:
$$p=6308948,\qquad M(10)=432256955,\qquad M(10000)=3264567774119.$$
هذه القيم مهمة لأنها تتحقق من بناء الدورة ومن قاعدة الصرامة على اليسار وعدم الصرامة على اليمين قبل الانتقال إلى الحساب النهائي عند \(N=2\cdot 10^9\).
بناء دورة واحدة يحتاج إلى \(O(p)\) زمنًا. وكل مرور باستخدام stack أحادي الرتابة يحتاج أيضًا إلى \(O(p)\)، لأن كل موضع يُدفع ويُسحب مرة واحدة على الأكثر. كما أن التجميع النهائي على جميع مواضع الدورة وعددها \(p\) هو \(O(p)\) مرة أخرى. لذلك تعمل الخوارزمية كلها في \(O(p)\) زمنًا و\(O(p)\) ذاكرة، حيث \(p=6308948\)، بينما يدخل \(N\) الضخم فقط عبر العددين \(q\) و\(r\).