The sequence is defined by
$$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$$
where \(B(m)\) denotes the number of \(1\)-bits in the binary expansion of \(m\). For each prefix multiset \(\{u_1,\dots,u_n\}\) with \(n\ge4\), we choose four values \(a\le b\le c\le d\) and form the quadrilateral with maximum possible area from those side lengths. If several choices have the same maximal area, we keep the one with larger perimeter \(a+b+c+d\). Let \(f(n)\) be that perimeter. The task is to compute
$$\sum_{n=4}^{3000000} f(n).$$
A brute-force search over all quadruples of every prefix is hopeless. The implementation works because the geometric score has a strong monotonicity property: once the largest side is fixed, the other three sides should be as large as possible. That turns the problem into maintaining only consecutive 4-blocks in the sorted prefix.
Write the sorted prefix as
$$x_1\le x_2\le \cdots \le x_n.$$
Any candidate for the prefix \(n\) is a quadruple
$$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n.$$
Because the input is a multiset, equal values are allowed and must be counted with their multiplicities. The objective for each prefix is not merely to find a valid quadrilateral, but to find the valid quadrilateral whose area is maximal, using perimeter only as a tie-breaker.
For sorted sides \(a\le b\le c\le d\), a non-degenerate quadrilateral exists exactly when
$$d<a+b+c.$$
Among all quadrilaterals with those four side lengths, the maximal area is attained by a cyclic quadrilateral. If
$$s=\frac{a+b+c+d}{2},$$
then Brahmagupta's formula gives
$$A^2=(s-a)(s-b)(s-c)(s-d).$$
Multiplying by \(16\) removes the fractions, so the implementations compare the integer score
$$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$$
Since \(Q=16A^2\), maximizing area is equivalent to maximizing \(Q\). If two candidates have the same \(Q\), the larger perimeter
$$P=a+b+c+d$$
wins.
Fix the largest chosen side \(d\). Inside the valid region \(d<a+b+c\), consider \(Q(a,b,c,d)\) while \(d\) is fixed. For example, with \(b,c,d\) fixed,
$$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$$
Because \(a\le b\le c\le d\), each denominator in the positive terms is at most \(b+c+d-a\). Therefore the derivative is positive, so \(Q\) increases as \(a\) increases. The same one-line monotonicity check works for \(b\) and \(c\) as well.
So once the largest selected value is \(x_t\), the score is maximized by taking the three largest available predecessors:
$$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$$
If even this consecutive block fails the inequality \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\), then every other choice with largest side \(x_t\) also fails, because the sum of the other three sides can only get smaller. Hence every optimal candidate in a prefix is one of the consecutive sorted blocks
$$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$$
Suppose the next value is inserted into the sorted prefix at position \(p\) using \(0\)-based indexing. All consecutive 4-blocks that do not contain this new element are unchanged, so the previous best remains valid unless one of the new blocks beats it.
The only consecutive 4-blocks containing position \(p\) are those starting at
$$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4].$$
Every one of those blocks lies inside the seven-element window
$$[\max(0,p-3),\ \min(n-1,p+3)].$$
Therefore each update needs only a constant-size neighborhood: extract that tiny sorted window, test at most four blocks, and compare them with the running global best.
The first five sequence values are
$$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$$
So the sorted prefix is
$$8,9,9,14,27.$$
The consecutive candidates are \((8,9,9,14)\) and \((9,9,14,27)\).
For \((8,9,9,14)\),
$$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$$
For \((9,9,14,27)\),
$$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$$
So the second block wins, and therefore
$$f(5)=59.$$
This is exactly the kind of local comparison performed at each insertion.
The C++, Python, and Java implementations first generate all values \(u_n\) up to \(N=3000000\). They precompute the small tables of powers of \(2\) and \(3\), because only the population counts vary from one index to the next.
Next, the implementations coordinate-compress all generated values. The sorted prefix multiset is then maintained by an order-statistics Fenwick tree over the compressed ranks. This supports three operations in logarithmic time: insert the next value, count how many current elements are strictly smaller, and recover the value at any requested sorted position.
After each insertion, the implementation finds the new sorted position \(p\), extracts the window from \(p-3\) to \(p+3\), evaluates the at most four consecutive 4-blocks that contain the new element, and updates the global best by comparing first the score \(Q\) and then the perimeter. The winning perimeter for the current prefix is added to the final sum.
The score \(Q\) is a product of four potentially large factors, so the implementations use sufficiently wide integer arithmetic when performing that comparison.
Generating the sequence costs \(O(N)\). Coordinate compression requires sorting the generated values, so preprocessing costs \(O(N\log N)\) time. During the sweep, each Fenwick-tree insertion and each order-statistics query costs \(O(\log M)\), where \(M\) is the number of distinct sequence values, and only a constant number of candidate blocks are tested per prefix. Thus the overall running time is \(O(N\log N)\), and the memory usage is \(O(N)\).
Die Folge ist definiert durch
$$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$$
wobei \(B(m)\) die Anzahl der \(1\)-Bits in der Binärdarstellung von \(m\) ist. Für jedes Präfix-Multiset \(\{u_1,\dots,u_n\}\) mit \(n\ge4\) wählen wir vier Werte \(a\le b\le c\le d\) und betrachten unter genau diesen Seitenlängen das Viereck mit maximal möglicher Fläche. Haben mehrere Wahlen dieselbe maximale Fläche, entscheidet der größere Umfang \(a+b+c+d\). Dieser Umfang sei \(f(n)\). Gesucht ist
$$\sum_{n=4}^{3000000} f(n).$$
Ein vollständiges Durchprobieren aller Vierer-Auswahlen in jedem Präfix wäre viel zu langsam. Die Implementierung nutzt daher zwei Strukturbeobachtungen aus: Ist die größte Seite fest, dann sollten die drei anderen Seiten so groß wie möglich sein; und nach dem Einfügen eines neuen Werts entstehen nur vier neue aufeinanderfolgende 4er-Blöcke.
Schreiben wir das sortierte Präfix als
$$x_1\le x_2\le \cdots \le x_n.$$
Jeder Kandidat für das Präfix \(n\) ist dann ein Viererblock
$$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n.$$
Da das Eingabeobjekt ein Multiset ist, dürfen gleiche Werte mehrfach vorkommen und müssen mit ihrer Vielfachheit behandelt werden. Gesucht ist also nicht einfach irgendein gültiges Viereck, sondern das gültige Viereck mit maximaler Fläche; nur bei Gleichstand entscheidet der Umfang.
Für sortierte Seiten \(a\le b\le c\le d\) existiert genau dann ein nicht entartetes Viereck, wenn
$$d<a+b+c.$$
Unter allen Vierecken mit diesen vier Seitenlängen wird die maximale Fläche von einem zyklischen Viereck erreicht. Mit
$$s=\frac{a+b+c+d}{2}$$
liefert die Brahmagupta-Formel
$$A^2=(s-a)(s-b)(s-c)(s-d).$$
Durch Multiplikation mit \(16\) verschwinden die Brüche, daher vergleichen die Implementierungen den ganzzahligen Score
$$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$$
Wegen \(Q=16A^2\) ist das Maximieren der Fläche genau dasselbe wie das Maximieren von \(Q\). Bei Gleichstand gewinnt der größere Umfang
$$P=a+b+c+d.$$
Fixiere die größte gewählte Seite \(d\). Innerhalb des gültigen Bereichs \(d<a+b+c\) betrachten wir \(Q(a,b,c,d)\) bei festem \(d\). Für festes \(b,c,d\) gilt zum Beispiel
$$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$$
Wegen \(a\le b\le c\le d\) ist jeder Nenner der positiven Terme höchstens \(b+c+d-a\). Also ist die Ableitung positiv, und \(Q\) wächst mit \(a\). Dieselbe kurze Monotonieprüfung funktioniert ebenso für \(b\) und \(c\).
Sobald also der größte gewählte Wert \(x_t\) feststeht, wird der Score maximiert, indem man die drei größten verfügbaren Vorgänger nimmt:
$$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$$
Falls schon dieser aufeinanderfolgende Block die Ungleichung \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\) nicht erfüllt, dann scheitert auch jede andere Wahl mit derselben größten Seite \(x_t\), weil die Summe der übrigen drei Seiten nur kleiner werden kann. Daher ist jeder optimale Kandidat eines Präfixes einer der aufeinanderfolgenden sortierten Blöcke
$$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$$
Angenommen, der nächste Wert wird an Position \(p\) in das sortierte Präfix eingefügt, wobei \(0\)-basierte Indizierung verwendet wird. Alle aufeinanderfolgenden 4er-Blöcke, die dieses neue Element nicht enthalten, bleiben unverändert. Der bisherige beste Block bleibt also Kandidat, es sei denn, einer der neuen Blöcke schlägt ihn.
Die einzigen aufeinanderfolgenden 4er-Blöcke, die Position \(p\) enthalten, starten bei
$$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4].$$
Jeder dieser Blöcke liegt vollständig im Siebenerfenster
$$[\max(0,p-3),\ \min(n-1,p+3)].$$
Damit genügt pro Update eine Nachbarschaft konstanter Größe: dieses kleine sortierte Fenster auslesen, höchstens vier Blöcke testen und gegen das laufende globale Optimum vergleichen.
Die ersten fünf Folgenglieder sind
$$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$$
Damit lautet das sortierte Präfix
$$8,9,9,14,27.$$
Die aufeinanderfolgenden Kandidaten sind \((8,9,9,14)\) und \((9,9,14,27)\).
Für \((8,9,9,14)\) gilt
$$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$$
Für \((9,9,14,27)\) gilt
$$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$$
Also gewinnt der zweite Block, und damit ist
$$f(5)=59.$$
Genau diese lokale Gegenüberstellung wiederholt der Algorithmus nach jeder Einfügung.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst alle Werte \(u_n\) bis \(N=3000000\). Dazu werden kleine Potenztabellen für \(2\) und \(3\) vorab berechnet, weil sich von Index zu Index nur die Popcount-Werte ändern.
Anschließend werden alle erzeugten Werte koordinatenkomprimiert. Das sortierte Präfix-Multiset wird dann über einen Fenwick-Baum mit Ordnungsstatistik auf den komprimierten Rängen verwaltet. Damit lassen sich in logarithmischer Zeit drei Operationen ausführen: den nächsten Wert einfügen, die Anzahl strikt kleinerer aktueller Werte bestimmen und den Wert an einer beliebigen sortierten Position zurückholen.
Nach jeder Einfügung bestimmt die Implementierung die neue sortierte Position \(p\), liest das Fenster von \(p-3\) bis \(p+3\) aus, bewertet die höchstens vier aufeinanderfolgenden 4er-Blöcke, die das neue Element enthalten, und aktualisiert das globale Optimum durch Vergleich von zuerst \(Q\) und dann dem Umfang. Der Gewinnerumfang des aktuellen Präfixes wird zur Endsumme addiert.
Da \(Q\) das Produkt von vier potenziell großen Faktoren ist, verwenden die Implementierungen für diesen Vergleich hinreichend breite Ganzzahlarithmetik.
Das Erzeugen der Folge kostet \(O(N)\). Für die Koordinatenkompression müssen die erzeugten Werte sortiert werden, also kostet die Vorverarbeitung \(O(N\log N)\) Zeit. Während des Sweeps kosten jede Fenwick-Einfügung und jede Ordnungsstatistik-Abfrage \(O(\log M)\), wobei \(M\) die Anzahl der verschiedenen Folgenglieder ist, und pro Präfix werden nur konstant viele Kandidatenblöcke geprüft. Insgesamt ergibt sich damit \(O(N\log N)\) Laufzeit und \(O(N)\) Speicherbedarf.
Dizi şu şekilde tanımlanır:
$$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$$
burada \(B(m)\), \(m\)'nin ikilik yazımındaki \(1\) bitlerinin sayısıdır. Her \(n\ge4\) için \(\{u_1,\dots,u_n\}\) ön-ek çoklu kümesinden \(a\le b\le c\le d\) olacak şekilde dört değer seçilir ve bu kenar uzunluklarıyla elde edilebilecek en büyük alana sahip dörtgen dikkate alınır. Birden fazla seçim aynı en büyük alanı verirse çevresi daha büyük olan tercih edilir. Bu çevreye \(f(n)\) diyelim. İstenen toplam
$$\sum_{n=4}^{3000000} f(n)$$
değeridir.
Her ön-ekteki tüm dörtlüleri kaba kuvvetle denemek mümkün değildir. Uygulamanın çalışmasını sağlayan iki temel yapı vardır: en büyük kenar sabitken diğer üç kenar mümkün olduğunca büyük seçilmelidir ve yeni bir değer eklendiğinde yalnızca dört yeni ardışık 4'lü blok ortaya çıkar.
Sıralanmış ön-eki
$$x_1\le x_2\le \cdots \le x_n$$
şeklinde yazalım. O zaman ön-ek \(n\) için her aday dörtlü
$$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n$$
biçimindedir. Giriş bir çoklu küme olduğu için eşit değerler tekrar tekrar gelebilir ve çokluklarıyla birlikte ele alınmalıdır. Dolayısıyla hedef yalnızca geçerli bir dörtgen bulmak değil, alanı en büyük olan geçerli dörtgeni bulmaktır; çevre sadece eşitlik bozucudur.
Sıralı kenarlar \(a\le b\le c\le d\) için dejenere olmayan bir dörtgenin var olması için ve ancak bunun için
$$d<a+b+c$$
gerekir. Bu dört kenarla çizilebilecek dörtgenler arasında en büyük alan çevrel dörtgende elde edilir. Eğer
$$s=\frac{a+b+c+d}{2}$$
ise Brahmagupta formülü
$$A^2=(s-a)(s-b)(s-c)(s-d)$$
der. Kesirlerden kurtulmak için implementasyonlar şu tam sayı skorunu karşılaştırır:
$$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$$
Çünkü \(Q=16A^2\), alanı maksimize etmek ile \(Q\)'yu maksimize etmek aynı şeydir. Eşit \(Q\) durumunda daha büyük çevre
$$P=a+b+c+d$$
kazanır.
Seçilmiş en büyük kenarı \(d\) olarak sabitleyelim. Geçerli bölge olan \(d<a+b+c\) içinde, \(d\) sabitken \(Q(a,b,c,d)\)'yi inceleyelim. Örneğin \(b,c,d\) sabitken
$$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$$
\(a\le b\le c\le d\) olduğundan pozitif terimlerdeki her payda \(b+c+d-a\) değerinden büyük değildir. Bu yüzden türev pozitiftir ve \(Q\), \(a\) arttıkça artar. Aynı kısa monotonluk kontrolü \(b\) ve \(c\) için de geçerlidir.
Sonuç olarak en büyük seçili değer \(x_t\) sabitken en iyi skor, ondan önce gelen üç mümkün olan en büyük değeri seçerek elde edilir:
$$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$$
Eğer bu ardışık blok bile \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\) koşulunu sağlamıyorsa, aynı en büyük kenar \(x_t\) ile başka hiçbir seçim başarılı olamaz; çünkü diğer üç kenarın toplamı ancak daha küçük olabilir. Demek ki her ön-ekteki en iyi aday mutlaka şu ardışık bloklardan biridir:
$$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$$
Bir sonraki değer sıralı ön-eke \(0\)-bazlı indeksle \(p\) konumunda eklenmiş olsun. Bu yeni elemanı içermeyen tüm ardışık 4'lü bloklar değişmeden kalır. Yani eski en iyi blok hâlâ adaydır; onu yalnızca yeni bloklardan biri geçebilir.
\(p\) konumunu içeren tek ardışık 4'lü blokların başlangıçları
$$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4]$$
kümesindedir. Bu blokların hepsi şu yedi elemanlı pencerenin içindedir:
$$[\max(0,p-3),\ \min(n-1,p+3)].$$
Dolayısıyla her güncellemede sabit boyutlu çok küçük bir komşuluk yeterlidir: bu pencereyi çıkar, en fazla dört blok dene ve bunları eldeki küresel en iyiyle karşılaştır.
İlk beş dizi terimi şöyledir:
$$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$$
Böylece sıralı ön-ek
$$8,9,9,14,27$$
olur. Ardışık aday bloklar \((8,9,9,14)\) ve \((9,9,14,27)\)'dir.
\((8,9,9,14)\) için
$$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$$
\((9,9,14,27)\) için
$$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$$
Bu nedenle ikinci blok kazanır ve
$$f(5)=59$$
olur. Algoritmanın her eklemede yaptığı yerel karşılaştırma tam olarak budur.
C++, Python ve Java implementasyonları önce \(N=3000000\) sınırına kadar tüm \(u_n\) değerlerini üretir. Bunu hızlandırmak için \(2\) ve \(3\)'ün küçük üs tabloları önceden hazırlanır; çünkü indeksten indekse değişen şey yalnızca popcount değerleridir.
Daha sonra üretilen tüm değerler koordinat sıkıştırmasına tabi tutulur. Sıralı ön-ek çoklu kümesi, sıkıştırılmış dereceler üzerinde çalışan sıralama-istatistikli bir Fenwick ağacı ile tutulur. Böylece üç işlem logaritmik zamanda yapılır: yeni değeri eklemek, ondan kesin küçük kaç eleman olduğunu bulmak ve istenen sıralı konumdaki değeri geri almak.
Her eklemeden sonra implementasyon yeni sıralı konum \(p\)'yi bulur, \(p-3\) ile \(p+3\) arasındaki pencereyi çıkarır, yeni elemanı içeren en fazla dört ardışık 4'lü bloğu değerlendirir ve önce \(Q\), sonra çevre ile küresel en iyiyi günceller. O anki ön-ek için kazanan çevre sonuca eklenir.
\(Q\), dört büyük çarpanın çarpımı olduğundan implementasyonlar bu karşılaştırmada yeterince geniş tamsayı aritmetiği kullanır.
Diziyi üretmek \(O(N)\) sürer. Koordinat sıkıştırması için üretilen değerlerin sıralanması gerektiğinden ön işleme maliyeti \(O(N\log N)\) zamandır. Tarama sırasında her Fenwick eklemesi ve her sıralama-istatistiği sorgusu \(O(\log M)\) zaman alır; burada \(M\), farklı dizi değeri sayısıdır. Her ön-ekte yalnızca sabit sayıda aday blok test edildiği için toplam süre \(O(N\log N)\), bellek kullanımı ise \(O(N)\) olur.
La sucesión está definida por
$$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$$
donde \(B(m)\) es el número de bits iguales a \(1\) en la representación binaria de \(m\). Para cada prefijo multiconjunto \(\{u_1,\dots,u_n\}\) con \(n\ge4\), elegimos cuatro valores \(a\le b\le c\le d\) y consideramos el cuadrilátero de área máxima que puede construirse con esas longitudes. Si varias elecciones producen la misma área máxima, se conserva la de mayor perímetro \(a+b+c+d\). Llamemos \(f(n)\) a ese perímetro. Hay que calcular
$$\sum_{n=4}^{3000000} f(n).$$
Probar todas las cuádruplas en cada prefijo es imposible. La implementación se apoya en dos hechos estructurales: una vez fijado el lado mayor, los otros tres deben ser lo más grandes posible; y, tras insertar un nuevo valor, solo aparecen cuatro bloques consecutivos de longitud \(4\) que antes no existían.
Escribamos el prefijo ordenado como
$$x_1\le x_2\le \cdots \le x_n.$$
Cada candidato para el prefijo \(n\) es entonces una cuádrupla
$$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n.$$
Como la entrada es un multiconjunto, los valores repetidos pueden aparecer varias veces y deben tratarse con su multiplicidad. El objetivo no es simplemente encontrar un cuadrilátero válido, sino el cuadrilátero válido con área máxima; el perímetro solo se usa para desempatar.
Para lados ordenados \(a\le b\le c\le d\), existe un cuadrilátero no degenerado exactamente cuando
$$d<a+b+c.$$
Entre todos los cuadriláteros con esos cuatro lados, el área máxima la alcanza un cuadrilátero cíclico. Si
$$s=\frac{a+b+c+d}{2},$$
la fórmula de Brahmagupta da
$$A^2=(s-a)(s-b)(s-c)(s-d).$$
Multiplicar por \(16\) elimina las fracciones, así que las implementaciones comparan la puntuación entera
$$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$$
Como \(Q=16A^2\), maximizar el área es equivalente a maximizar \(Q\). Si dos candidatos tienen el mismo \(Q\), gana el mayor perímetro
$$P=a+b+c+d.$$
Fijemos el lado mayor \(d\). En la región válida \(d<a+b+c\), estudiamos \(Q(a,b,c,d)\) con \(d\) fijo. Por ejemplo, manteniendo fijos \(b,c,d\), se cumple
$$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$$
Como \(a\le b\le c\le d\), cada denominador de los términos positivos es a lo sumo \(b+c+d-a\). Por tanto la derivada es positiva y \(Q\) crece cuando \(a\) crece. La misma comprobación de monotonía funciona también para \(b\) y \(c\).
Así, una vez fijado el mayor valor elegido \(x_t\), la mejor puntuación se obtiene tomando los tres mayores predecesores disponibles:
$$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$$
Si incluso este bloque consecutivo no satisface \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\), entonces cualquier otra elección con el mismo lado mayor \(x_t\) también falla, porque la suma de los otros tres lados solo puede disminuir. En consecuencia, todo candidato óptimo en un prefijo es uno de los bloques consecutivos ordenados
$$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$$
Supongamos que el siguiente valor se inserta en la posición \(p\) del prefijo ordenado, usando índices basados en \(0\). Todos los bloques consecutivos de longitud \(4\) que no contienen ese nuevo elemento permanecen iguales. Por eso, el mejor bloque anterior sigue siendo candidato salvo que uno de los bloques nuevos lo mejore.
Los únicos bloques consecutivos de longitud \(4\) que contienen la posición \(p\) son los que empiezan en
$$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4].$$
Cada uno de ellos queda dentro de la ventana de siete elementos
$$[\max(0,p-3),\ \min(n-1,p+3)].$$
Por tanto, cada actualización solo necesita un vecindario de tamaño constante: extraer esa pequeña ventana ordenada, probar como mucho cuatro bloques y compararlos con el mejor global acumulado.
Los cinco primeros términos de la sucesión son
$$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$$
Luego el prefijo ordenado es
$$8,9,9,14,27.$$
Los candidatos consecutivos son \((8,9,9,14)\) y \((9,9,14,27)\).
Para \((8,9,9,14)\),
$$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$$
Para \((9,9,14,27)\),
$$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$$
Así que gana el segundo bloque, y por tanto
$$f(5)=59.$$
Ese es exactamente el tipo de comparación local que repite el algoritmo en cada inserción.
Las implementaciones en C++, Python y Java generan primero todos los valores \(u_n\) hasta \(N=3000000\). Para acelerar ese paso, precalculan pequeñas tablas de potencias de \(2\) y de \(3\), ya que lo único que cambia con \(n\) es el valor de los popcounts.
Después comprimen coordenadas sobre todos los valores generados. El multiconjunto ordenado del prefijo se mantiene entonces mediante un árbol de Fenwick con estadísticas de orden sobre los rangos comprimidos. Esto permite en tiempo logarítmico insertar el siguiente valor, contar cuántos elementos actuales son estrictamente menores y recuperar el valor situado en cualquier posición ordenada pedida.
Tras cada inserción, la implementación localiza la nueva posición ordenada \(p\), extrae la ventana de \(p-3\) a \(p+3\), evalúa los como mucho cuatro bloques consecutivos que contienen el nuevo elemento y actualiza el mejor global comparando primero \(Q\) y después el perímetro. El perímetro ganador del prefijo actual se añade a la suma final.
Como \(Q\) es el producto de cuatro factores potencialmente grandes, las implementaciones usan aritmética entera suficientemente ancha al realizar esa comparación.
Generar la sucesión cuesta \(O(N)\). La compresión de coordenadas requiere ordenar los valores generados, así que el preprocesamiento cuesta \(O(N\log N)\) tiempo. Durante el recorrido, cada inserción en el árbol de Fenwick y cada consulta de estadística de orden cuesta \(O(\log M)\), donde \(M\) es el número de valores distintos de la sucesión, y en cada prefijo solo se prueban un número constante de bloques candidatos. En total, el tiempo de ejecución es \(O(N\log N)\) y el uso de memoria es \(O(N)\).
数列定义为
$$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$$
其中 \(B(m)\) 表示 \(m\) 的二进制表示中 \(1\) 的个数。对每个 \(n\ge4\) 的前缀多重集 \(\{u_1,\dots,u_n\}\)，从中选出四个值 \(a\le b\le c\le d\)，并考虑用这四条边能够构成的最大面积四边形。如果有多个选择得到相同的最大面积，就取周长 \(a+b+c+d\) 更大的那个。记这个周长为 \(f(n)\)。题目要求计算
$$\sum_{n=4}^{3000000} f(n).$$
如果对每个前缀都枚举所有四元组，计算量会大到不可接受。实现之所以可行，是因为这里有两个关键结构性质：固定最大边以后，其余三条边应该尽量大；而插入一个新值以后，真正新增的候选只会是四个相邻的长度为 \(4\) 的块。
把排好序的前缀记为
$$x_1\le x_2\le \cdots \le x_n.$$
那么前缀 \(n\) 的任意一个候选都可以写成
$$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n.$$
由于这里处理的是多重集，相同的数值可以出现多次，必须按出现次数保留。对每个前缀，我们的目标不是随便找到一个能成四边形的四元组，而是找到面积最大的那个；只有当面积完全相同时，才用周长来决定胜负。
对排好序的边长 \(a\le b\le c\le d\)，存在非退化四边形当且仅当
$$d<a+b+c.$$
对于给定的四条边，面积最大的四边形一定是圆内接四边形。若记半周长为
$$s=\frac{a+b+c+d}{2},$$
那么 Brahmagupta 公式给出
$$A^2=(s-a)(s-b)(s-c)(s-d).$$
把式子乘以 \(16\) 后就没有分数了，因此实现中实际比较的是下面这个整数评分：
$$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$$
因为 \(Q=16A^2\)，所以最大化面积与最大化 \(Q\) 完全等价。如果两个候选的 \(Q\) 相同，就选周长
$$P=a+b+c+d$$
更大的那个。
先把最大边 \(d\) 固定住。在有效区域 \(d<a+b+c\) 内，考察 \(Q(a,b,c,d)\) 随较小三条边变化的规律。比如在 \(b,c,d\) 固定时，有
$$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$$
由于 \(a\le b\le c\le d\)，上式中三个正项的分母都不大于 \(b+c+d-a\)。因此导数为正，说明 \(a\) 变大时 \(Q\) 会变大。对 \(b\) 和 \(c\) 做同样的单行检查，也能得到同样的单调性结论。
这意味着：一旦最大边选定为 \(x_t\)，想让评分最大，就应该把其余三条边也尽量取得更大，也就是直接取它前面的三个最大元素：
$$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$$
如果连这个相邻块都不满足 \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\)，那么任何以 \(x_t\) 为最大边的其他选择也都不可能成功，因为另外三条边之和只会更小。于是，前缀中的最优候选一定属于这些相邻的有序四元组：
$$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$$
设新值插入到当前有序前缀中的位置是 \(p\)，这里使用 \(0\) 基下标。不包含这个新元素的所有相邻四元组都与上一步完全相同，所以旧的最优答案仍然有效，除非某个新块超过它。
唯一包含位置 \(p\) 的长度为 \(4\) 的相邻块，其起点只能是
$$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4].$$
这些块全部落在一个至多七个元素的局部窗口内：
$$[\max(0,p-3),\ \min(n-1,p+3)].$$
因此每次更新只需要查看一个常数大小的邻域：取出这段很小的有序窗口，检查至多四个候选块，再与当前全局最优比较即可。
前五项数列值为
$$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$$
于是排序后的前缀是
$$8,9,9,14,27.$$
相邻候选块只有两个：\((8,9,9,14)\) 和 \((9,9,14,27)\)。
对 \((8,9,9,14)\)，
$$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$$
对 \((9,9,14,27)\)，
$$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$$
所以第二个块更优，从而
$$f(5)=59.$$
算法在每一步做的，本质上就是这种局部比较。
C++、Python 和 Java 实现首先生成全部 \(u_n\)，直到 \(N=3000000\)。为了加快这一步，它们会预先准备好 \(2\) 和 \(3\) 的小型幂表，因为随 \(n\) 变化的只有 popcount 的结果。
接下来，所有生成出的数值会做坐标压缩。随后，排好序的前缀多重集通过一个建立在压缩秩上的 Fenwick 树来维护顺序统计信息。这样就能在对数时间内完成三件事：插入下一个值，统计当前有多少元素严格更小，以及取回当前前缀中任意指定有序位置上的数值。
每插入一个新值，实现都会先找到它的新有序位置 \(p\)，取出从 \(p-3\) 到 \(p+3\) 的局部窗口，枚举其中至多四个包含新元素的相邻四元组，然后按照先比较 \(Q\)、再比较周长的规则更新全局最优。当前前缀的获胜周长会被加入最终答案。
由于 \(Q\) 是四个可能很大的因子的乘积，实现会使用足够宽的整数类型来完成这个比较。
生成数列本身需要 \(O(N)\) 时间。坐标压缩需要对生成值排序，因此预处理时间为 \(O(N\log N)\)。在后续扫描过程中，每次 Fenwick 树插入和每次顺序统计查询都需要 \(O(\log M)\) 时间，其中 \(M\) 是不同数值的个数，而每个前缀只会检查常数个候选块。所以总体时间复杂度为 \(O(N\log N)\)，空间复杂度为 \(O(N)\)。
Последовательность задается формулой
$$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$$
где \(B(m)\) обозначает количество единичных битов в двоичной записи числа \(m\). Для каждого префиксного мультимножества \(\{u_1,\dots,u_n\}\) при \(n\ge4\) нужно выбрать четыре значения \(a\le b\le c\le d\) и рассмотреть четырехугольник максимальной возможной площади с такими длинами сторон. Если несколько вариантов дают одну и ту же максимальную площадь, выбирается тот, у которого больше периметр \(a+b+c+d\). Обозначим этот периметр через \(f(n)\). Требуется найти
$$\sum_{n=4}^{3000000} f(n).$$
Полный перебор всех четверок в каждом префиксе слишком дорог. Реализация опирается на два структурных факта: при фиксированной наибольшей стороне три остальные должны быть как можно больше, а после вставки нового значения появляются лишь четыре новых последовательных блока длины \(4\).
Обозначим отсортированный префикс как
$$x_1\le x_2\le \cdots \le x_n.$$
Тогда любой кандидат для префикса \(n\) имеет вид
$$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n.$$
Поскольку речь идет о мультимножестве, одинаковые значения могут встречаться несколько раз и должны учитываться со своей кратностью. Значит, цель состоит не просто в поиске корректного четырехугольника, а в поиске корректного четырехугольника максимальной площади; периметр нужен только для разрешения ничьих.
Для упорядоченных сторон \(a\le b\le c\le d\) невырожденный четырехугольник существует тогда и только тогда, когда
$$d<a+b+c.$$
Среди всех четырехугольников с такими сторонами максимальную площадь имеет вписанный четырехугольник. Если
$$s=\frac{a+b+c+d}{2},$$
то формула Брахмагупты дает
$$A^2=(s-a)(s-b)(s-c)(s-d).$$
Умножение на \(16\) убирает дроби, поэтому в реализации сравнивается целочисленная оценка
$$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$$
Так как \(Q=16A^2\), максимизация площади эквивалентна максимизации \(Q\). При равных \(Q\) побеждает больший периметр
$$P=a+b+c+d.$$
Зафиксируем наибольшую сторону \(d\). Внутри допустимой области \(d<a+b+c\) рассмотрим \(Q(a,b,c,d)\) при фиксированном \(d\). Например, при фиксированных \(b,c,d\) имеем
$$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$$
Поскольку \(a\le b\le c\le d\), каждый знаменатель в положительных слагаемых не превосходит \(b+c+d-a\). Следовательно, производная положительна, а значит \(Q\) возрастает при увеличении \(a\). Тот же короткий аргумент монотонности работает и для \(b\), и для \(c\).
Отсюда следует: если наибольшее выбранное значение равно \(x_t\), то максимальный score получается, когда мы берем три наибольших доступных предшественника:
$$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$$
Если даже этот последовательный блок не удовлетворяет неравенству \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\), то любая другая четверка с той же наибольшей стороной \(x_t\) тоже не подойдет, потому что сумма трех остальных сторон станет только меньше. Значит, любой оптимальный кандидат в префиксе обязан быть одним из последовательных отсортированных блоков
$$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$$
Пусть следующее значение вставляется в отсортированный префикс на позицию \(p\), где используется нумерация с нуля. Все последовательные блоки длины \(4\), не содержащие новый элемент, остаются без изменений. Поэтому прежний лучший блок по-прежнему является кандидатом, если только один из новых блоков его не превзойдет.
Единственные последовательные блоки длины \(4\), содержащие позицию \(p\), начинаются в точках
$$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4].$$
Каждый такой блок целиком лежит в окне из семи элементов
$$[\max(0,p-3),\ \min(n-1,p+3)].$$
Значит, на каждом шаге достаточно рассмотреть окрестность постоянного размера: извлечь это маленькое отсортированное окно, проверить не более четырех блоков и сравнить их с текущим глобальным максимумом.
Первые пять значений последовательности таковы:
$$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$$
Следовательно, отсортированный префикс равен
$$8,9,9,14,27.$$
Последовательные кандидаты здесь только два: \((8,9,9,14)\) и \((9,9,14,27)\).
Для \((8,9,9,14)\)
$$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$$
Для \((9,9,14,27)\)
$$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$$
Следовательно, выигрывает второй блок, и потому
$$f(5)=59.$$
Именно такое локальное сравнение алгоритм выполняет после каждой вставки.
Реализации на C++, Python и Java сначала генерируют все значения \(u_n\) вплоть до \(N=3000000\). Чтобы сделать это быстро, заранее подготавливаются небольшие таблицы степеней \(2\) и \(3\), поскольку от индекса к индексу меняются только значения popcount.
Затем все полученные значения подвергаются координатному сжатию. После этого отсортированное префиксное мультимножество поддерживается деревом Фенвика со статистиками порядка по сжатым рангам. Это дает три логарифмические операции: вставить следующее значение, посчитать количество строго меньших текущих элементов и восстановить значение, стоящее на любой заданной позиции в отсортированном префиксе.
После каждой вставки реализация находит новую отсортированную позицию \(p\), извлекает окно от \(p-3\) до \(p+3\), оценивает не более четырех последовательных блоков длины \(4\), содержащих новый элемент, и обновляет глобальный максимум, сравнивая сначала \(Q\), а затем периметр. Победивший периметр для текущего префикса добавляется к окончательной сумме.
Так как \(Q\) является произведением четырех потенциально больших множителей, для этого сравнения используется достаточно широкая целочисленная арифметика.
Генерация последовательности требует \(O(N)\) времени. Координатное сжатие требует сортировки полученных значений, поэтому предобработка стоит \(O(N\log N)\) времени. Во время основного прохода каждая вставка в дерево Фенвика и каждый запрос статистики порядка работают за \(O(\log M)\), где \(M\) — число различных значений последовательности, а на каждом префиксе проверяется лишь константное число кандидатных блоков. Итак, полное время работы равно \(O(N\log N)\), а потребление памяти составляет \(O(N)\).
تُعرَّف المتتالية بالعلاقة
$$u_n=2^{B(3n)}+3^{B(2n)}+B(n+1),$$
حيث إن \(B(m)\) هو عدد البتات التي تساوي \(1\) في التمثيل الثنائي للعدد \(m\). ولكل بادئة متعددة العناصر \(\{u_1,\dots,u_n\}\) عندما \(n\ge4\)، نختار أربعة قيم \(a\le b\le c\le d\)، ثم ننظر إلى رباعي الأضلاع ذي المساحة العظمى الممكنة بهذه الأطوال. وإذا وجدت عدة اختيارات تعطي المساحة العظمى نفسها، نأخذ الاختيار ذي المحيط الأكبر \(a+b+c+d\). ولنرمز إلى هذا المحيط بـ \(f(n)\). المطلوب هو حساب
$$\sum_{n=4}^{3000000} f(n).$$
فحص جميع الرباعيات في كل بادئة غير عملي إطلاقًا. تعتمد الفكرة على حقيقتين بنيويتين: إذا ثبَّتنا أكبر ضلع فإن الأضلاع الثلاثة الأخرى يجب أن تكون أكبر ما يمكن، وبعد إدراج قيمة جديدة لا تظهر إلا أربع كتل متتالية جديدة طول كل منها \(4\).
لنكتب البادئة المرتبة على الصورة
$$x_1\le x_2\le \cdots \le x_n.$$
وعندئذ يكون كل مرشح للبادئة \(n\) رباعية من الشكل
$$x_i\le x_j\le x_k\le x_\ell,\qquad 1\le i<j<k<\ell\le n.$$
وبما أن المدخل متعدد عناصر، فيمكن أن تتكرر القيمة نفسها أكثر من مرة ويجب التعامل معها مع احتفاظها بتكرارها. لذلك فالمطلوب ليس مجرد إيجاد رباعي صالح، بل إيجاد الرباعي الصالح ذي المساحة العظمى، ويستعمل المحيط فقط لكسر التعادل.
إذا كانت الأضلاع مرتبة \(a\le b\le c\le d\)، فإن وجود رباعي غير منحل يكافئ تمامًا الشرط
$$d<a+b+c.$$
ومن بين جميع الرباعيات التي لها هذه الأضلاع، تتحقق المساحة العظمى في رباعي دائري. وإذا كان
$$s=\frac{a+b+c+d}{2},$$
فإن صيغة براهماغوبتا تعطي
$$A^2=(s-a)(s-b)(s-c)(s-d).$$
وبضرب الطرفين في \(16\) نتخلص من الكسور، لذلك تقارن التطبيقات الدرجة الصحيحة
$$Q(a,b,c,d)= \begin{cases} (a+b+c-d)(a+b-c+d)(a-b+c+d)(-a+b+c+d), & d<a+b+c,\\ 0, & d\ge a+b+c. \end{cases}$$
ولأن \(Q=16A^2\)، فإن تعظيم المساحة يكافئ تعظيم \(Q\). وإذا تساوت درجتان، يُفضَّل المحيط الأكبر
$$P=a+b+c+d.$$
لنثبت أكبر ضلع \(d\). داخل المنطقة الصالحة \(d<a+b+c\)، ندرس \(Q(a,b,c,d)\) عندما يكون \(d\) ثابتًا. مثلًا، إذا ثُبِّتت \(b,c,d\)، فإن
$$\frac{\partial}{\partial a}\log Q =-\frac{1}{b+c+d-a} +\frac{1}{a-b+c+d} +\frac{1}{a+b-c+d} +\frac{1}{a+b+c-d}.$$
وبما أن \(a\le b\le c\le d\)، فكل مقام في الحدود الموجبة لا يزيد على \(b+c+d-a\). ومن ثم تكون المشتقة موجبة، أي إن \(Q\) يزداد كلما ازداد \(a\). وينجح الفحص الأحادي نفسه أيضًا مع \(b\) و\(c\).
إذًا إذا كان أكبر عنصر مختار هو \(x_t\)، فإن أفضل درجة تتحقق باختيار أكبر ثلاثة أسلاف متاحين قبله مباشرة:
$$\bigl(x_{t-3},x_{t-2},x_{t-1},x_t\bigr).$$
وإذا كانت هذه الكتلة المتتالية نفسها لا تحقق الشرط \(x_t<x_{t-3}+x_{t-2}+x_{t-1}\)، فلن تنجح أي رباعية أخرى لها الضلع الأكبر نفسه \(x_t\)، لأن مجموع الأضلاع الثلاثة الأخرى لا يمكن إلا أن يكون أصغر. لذلك فكل مرشح أمثل في أي بادئة لا بد أن يكون واحدًا من الكتل المرتبة المتتالية
$$\bigl(x_i,x_{i+1},x_{i+2},x_{i+3}\bigr),\qquad 1\le i\le n-3.$$
لنفترض أن القيمة التالية أُدرجت في الموضع \(p\) داخل البادئة المرتبة، مع استعمال فهرسة تبدأ من الصفر. كل الكتل المتتالية ذات الطول \(4\) التي لا تحتوي العنصر الجديد تبقى كما هي. لذلك يظل أفضل مرشح سابق صالحًا للمقارنة ما لم تتفوق عليه إحدى الكتل الجديدة.
والكتل المتتالية الوحيدة ذات الطول \(4\) التي تحتوي الموضع \(p\) هي التي تبدأ عند
$$s\in \{p-3,p-2,p-1,p\}\cap [0,n-4].$$
وجميع هذه الكتل تقع داخل نافذة محلية طولها سبعة عناصر على الأكثر:
$$[\max(0,p-3),\ \min(n-1,p+3)].$$
وبالتالي فكل تحديث يحتاج فقط إلى حي صغير ثابت الحجم: نستخرج هذه النافذة المرتبة، ونفحص أربعة كتل على الأكثر، ثم نقارنها بأفضل نتيجة عالمية حتى تلك اللحظة.
أول خمسة حدود في المتتالية هي
$$u_1=8,\qquad u_2=9,\qquad u_3=14,\qquad u_4=9,\qquad u_5=27.$$
إذن تصبح البادئة المرتبة
$$8,9,9,14,27.$$
والمرشحان المتتاليان هما \((8,9,9,14)\) و\((9,9,14,27)\).
بالنسبة إلى \((8,9,9,14)\)، نحصل على
$$Q=12\cdot 22\cdot 22\cdot 24=139392,\qquad P=40.$$
وبالنسبة إلى \((9,9,14,27)\)، نحصل على
$$Q=5\cdot 31\cdot 41\cdot 41=260555,\qquad P=59.$$
إذن الكتلة الثانية أفضل، ومن ثم
$$f(5)=59.$$
وهذا بالضبط هو نوع المقارنة المحلية الذي تكرره الخوارزمية عند كل إدراج.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع قيم \(u_n\) حتى \(N=3000000\). ولتسريع هذه الخطوة تُحسب مسبقًا جداول صغيرة لقوى \(2\) و\(3\)، لأن الذي يتغير مع \(n\) هو فقط قيم popcount.
بعد ذلك تُضغط الإحداثيات لجميع القيم المولدة. ثم تُدار البادئة المرتبة متعددة العناصر بواسطة شجرة Fenwick مزودة بإحصاءات ترتيب على الرتب المضغوطة. وهذا يتيح ثلاث عمليات بزمن لوغاريتمي: إدراج القيمة التالية، وحساب عدد العناصر الحالية الأصغر قطعًا، واسترجاع القيمة الموجودة في أي موضع مرتب مطلوب.
بعد كل إدراج، تحدد التطبيقات الموضع المرتب الجديد \(p\)، وتستخرج النافذة من \(p-3\) إلى \(p+3\)، ثم تقيم الكتل الأربع المتتالية على الأكثر التي تحتوي العنصر الجديد، وتحدّث الأفضل عالميًا بمقارنة \(Q\) أولًا ثم المحيط ثانيًا. ويضاف المحيط الفائز للبادئة الحالية إلى المجموع النهائي.
ولأن \(Q\) هو حاصل ضرب أربعة عوامل قد تكون كبيرة، تستعمل التطبيقات حسابًا صحيحًا بعرض كاف عند تنفيذ هذه المقارنة.
توليد المتتالية يكلف \(O(N)\). أما ضغط الإحداثيات فيتطلب ترتيب القيم المولدة، ولذلك تكون كلفة المعالجة المسبقة \(O(N\log N)\) زمنيًا. وخلال المسح الرئيسي، كل عملية إدراج في شجرة Fenwick وكل استعلام لإحصاءات الترتيب يكلف \(O(\log M)\)، حيث \(M\) هو عدد القيم المختلفة في المتتالية، ولا يُفحص في كل بادئة إلا عدد ثابت من الكتل المرشحة. وعليه فإن زمن التنفيذ الكلي هو \(O(N\log N)\)، بينما يساوي استهلاك الذاكرة \(O(N)\).