Let \(M=50\,515\,093\) and \(s_0=290797\), with the pseudorandom recurrence
$$s_{n+1}=s_n^2 \bmod M.$$
For a given \(t\), the values are grouped into quadruples
$$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$$
Each quadruple defines an axis-aligned inclusive rectangle on the grid \(\{0,\dots,M-1\}^2\):
$$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$$
If \(c_t(x,y)\) is the number of rectangles covering the grid position \((x,y)\), then the displayed clock value is
$$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{otherwise.} \end{cases}$$
The required total is
$$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y)).$$
Since \(M^2\approx 2.55\times 10^{15}\), visiting every grid position directly is out of the question. The solution therefore counts whole strips of positions at once.
The core observation is that the final clock display depends only on the coverage count modulo \(12\). That turns the problem into a sweep-line computation over residue classes instead of raw counts.
On an integer grid, the inclusive rectangle
$$[x_1,x_2]\times[y_1,y_2]$$
covers exactly the same grid positions as the half-open box
$$[x_1,x_2+1)\times[y_1,y_2+1).$$
This reformulation is extremely useful because it means a rectangle starts affecting the sweep at \(x=x_1\) and stops affecting it at \(x=x_2+1\). Thus each rectangle contributes:
$$\text{entry event }(x_1,[y_1,y_2],+1),\qquad \text{exit event }(x_2+1,[y_1,y_2],-1).$$
If \(x_2=M-1\), then \(x_2+1=M\) lies just outside the grid, so no explicit exit event is needed inside the sweep. Between two consecutive event \(x\)-coordinates, the active set of rectangles is constant, which means the entire vertical strip has a fixed residue distribution along the \(y\)-axis.
The coverage pattern can change along \(y\) only at rectangle boundaries. Therefore it is enough to keep the sorted distinct breakpoints
$$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$$
After sorting them as
$$Y_0 \lt Y_1 \lt \dots \lt Y_m,$$
each elementary interval \([Y_j,Y_{j+1})\) is uniform: for a fixed \(x\)-strip, every active rectangle either covers that whole interval or misses it completely. So instead of tracking individual grid positions, we only need the integer length
$$\ell_j=Y_{j+1}-Y_j$$
of each compressed interval.
For any interval \(I\) in the segment tree, let
$$L_r(I)=\text{total }y\text{-length inside }I\text{ whose current coverage is }r \pmod{12},\qquad r=0,1,\dots,11.$$
Initially no rectangle is active, so every position has residue \(0\). Hence a leaf of length \(|I|\) starts with
$$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0.$$
When a rectangle starts on some \(y\)-range, every covered position has its coverage increased by \(1\), so the residue classes rotate:
$$L_r'(I)=L_{r-1 \bmod 12}(I).$$
When a rectangle ends, the update is \(-1\), which rotates in the opposite direction:
$$L_r'(I)=L_{r+1 \bmod 12}(I).$$
More generally, an update by \(\Delta\in\{-1,+1\}\) is just
$$L_r'(I)=L_{r-\Delta \bmod 12}(I).$$
That is why the implementation can use lazy propagation: each pending update is only a cyclic shift of a 12-component vector.
Let
$$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}.$$
Suppose the next event occurs at \(x=x_{\text{next}}\) and the current sweep position is \(x=x_{\text{cur}}\). The strip width is
$$w=x_{\text{next}}-x_{\text{cur}}.$$
During this whole strip, the root of the segment tree already knows the current \(y\)-lengths \(L_0,\dots,L_{11}\). Therefore we can add
$$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11).$$
After all strips have been accumulated, the clock total is reconstructed by remembering that residue \(0\) is displayed as \(12\):
$$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$$
Take a toy grid with coordinates \(\{0,1,2,3,4\}^2\) and two rectangles:
$$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$$
In half-open form these become
$$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5).$$
The \(x\)-events are at \(1,2,4,5\). Now examine the strips:
$$[0,1):\quad L_0=5.$$
$$[1,2):\quad L_1=3,\ L_0=2.$$
$$[2,4):\quad L_2=2,\ L_1=3.$$
$$[4,5):\quad L_1=4,\ L_0=1.$$
Multiplying by strip widths gives
$$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$$
$$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$$
$$C_2=2\cdot 2=4.$$
All other \(C_r\) are \(0\), and indeed \(8+13+4=25\), the whole grid. The weighted clock sum is
$$12\cdot 8+1\cdot 13+2\cdot 4=117.$$
This miniature example is exactly what the sweep-line algorithm does on the real input, only with a much larger coordinate range.
The C++, Python, and Java implementations follow the same pipeline. First they generate the pseudorandom sequence, take every four values as one rectangle, and normalize each rectangle so that the lower and upper coordinates are in sorted order. Then they build two derived datasets: a list of \(x\)-events and a sorted unique list of \(y\)-breakpoints for coordinate compression.
Next, the implementation builds a segment tree over the compressed \(y\)-intervals. Each leaf starts entirely in residue bucket \(0\), because before the sweep every grid position shows \(12\). Every internal node stores the total \(y\)-length in each of the 12 residue classes. A range update does not recompute coverage counts explicitly; it simply rotates the 12 stored totals, and the same rotation is saved as a lazy tag for descendants.
During the sweep, the implementation processes events in increasing \(x\). Before applying the events at the next coordinate, it multiplies the current strip width by the 12 residue lengths stored at the root and adds the results to the global residue totals. It then applies all entry and exit events at that \(x\)-coordinate as range rotations on the affected \(y\)-intervals. After the final event, one last strip up to \(x=M\) is accumulated.
Finally, the implementation converts the residue totals into the required clock sum by giving weight \(12\) to residue \(0\) and weights \(1\) through \(11\) to the remaining residues. The small checkpoints embedded in the implementations are consistent with this derivation, including the trivial case \(t=0\), where the answer is simply \(12M^2\).
Generating the rectangles takes \(O(t)\) time. There are at most \(2t\) sweep events and at most \(2t+2\) distinct \(y\)-breakpoints, so sorting costs \(O(t\log t)\). Each event performs one segment-tree range update in \(O(\log t)\), with only a fixed factor of \(12\) for the residue buckets. Therefore the overall running time is
$$O(t\log t),$$
and the memory usage is
$$O(t).$$
Sei \(M=50\,515\,093\) und \(s_0=290797\), mit der pseudorandomen Rekursion
$$s_{n+1}=s_n^2 \bmod M.$$
Für ein gegebenes \(t\) werden die Werte zu Viererblöcken zusammengefasst:
$$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$$
Jeder Viererblock definiert auf dem Gitter \(\{0,\dots,M-1\}^2\) ein achsenparalleles inklusives Rechteck:
$$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$$
Bezeichne mit \(c_t(x,y)\) die Anzahl der Rechtecke, die die Gitterposition \((x,y)\) überdecken. Dann ist der angezeigte Uhrenwert
$$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{sonst.} \end{cases}$$
Gesucht ist also
$$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y)).$$
Da \(M^2\approx 2.55\times 10^{15}\) ist, kann man das Gitter nicht direkt durchsuchen. Stattdessen zählt die Lösung ganze vertikale Streifen auf einmal.
Die Schlüsselerkenntnis lautet: Für die Endanzeige ist nur die Überdeckungszahl modulo \(12\) relevant. Damit wird das Problem zu einer Sweep-Line-Berechnung über Restklassen anstelle exakter Überdeckungszahlen.
Auf einem ganzzahligen Gitter überdeckt das inklusive Rechteck
$$[x_1,x_2]\times[y_1,y_2]$$
genau dieselben Gitterpositionen wie die halboffene Box
$$[x_1,x_2+1)\times[y_1,y_2+1).$$
Diese Umformung ist entscheidend: Ein Rechteck beginnt die Sweep-Line bei \(x=x_1\) zu beeinflussen und endet bei \(x=x_2+1\). Jedes Rechteck liefert also
$$\text{Start-Ereignis }(x_1,[y_1,y_2],+1),\qquad \text{End-Ereignis }(x_2+1,[y_1,y_2],-1).$$
Falls \(x_2=M-1\) gilt, liegt \(x_2+1=M\) bereits außerhalb des Gitters, also braucht man innerhalb des Sweeps kein explizites End-Ereignis mehr. Zwischen zwei aufeinanderfolgenden Ereigniswerten von \(x\) bleibt die aktive Rechteckmenge konstant, also auch die Verteilung der Restklassen entlang der \(y\)-Achse.
Das Überdeckungsmuster kann sich entlang von \(y\) nur an Rechteckgrenzen ändern. Deshalb reichen die sortierten verschiedenen Stützstellen
$$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$$
Nach dem Sortieren
$$Y_0 \lt Y_1 \lt \dots \lt Y_m$$
ist jedes elementare Intervall \([Y_j,Y_{j+1})\) homogen: Für einen festen \(x\)-Streifen bedeckt ein aktives Rechteck dieses Intervall entweder vollständig oder gar nicht. Daher genügt es, statt einzelner Gitterpunkte nur die ganzzahlige Länge
$$\ell_j=Y_{j+1}-Y_j$$
jedes komprimierten Intervalls zu speichern.
Für ein Intervall \(I\) des Segmentbaums sei
$$L_r(I)=\text{gesamte }y\text{-Länge in }I\text{ mit aktueller Überdeckung }r \pmod{12},\qquad r=0,1,\dots,11.$$
Anfangs ist kein Rechteck aktiv, also hat jede Position Restklasse \(0\). Ein Blatt der Länge \(|I|\) startet daher mit
$$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0.$$
Beginnt ein Rechteck auf einem \(y\)-Bereich, dann wird dort jede Überdeckungszahl um \(1\) erhöht, also rotieren die Restklassen:
$$L_r'(I)=L_{r-1 \bmod 12}(I).$$
Beim Ende eines Rechtecks ist das Update \(-1\), also rotiert der Vektor in die Gegenrichtung:
$$L_r'(I)=L_{r+1 \bmod 12}(I).$$
Allgemein ist ein Update um \(\Delta\in\{-1,+1\}\) einfach
$$L_r'(I)=L_{r-\Delta \bmod 12}(I).$$
Genau deshalb funktioniert Lazy Propagation: Ein ausstehendes Update ist nur eine zyklische Verschiebung eines 12-dimensionalen Vektors.
Definiere
$$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}.$$
Wenn das nächste Ereignis bei \(x=x_{\text{next}}\) liegt und die aktuelle Sweep-Position \(x=x_{\text{cur}}\) ist, dann hat der Streifen die Breite
$$w=x_{\text{next}}-x_{\text{cur}}.$$
Während dieses gesamten Streifens kennt die Wurzel des Segmentbaums bereits die aktuellen \(y\)-Längen \(L_0,\dots,L_{11}\). Daher addieren wir
$$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11).$$
Nach allen Streifen erhält man die Uhrensumme, indem Restklasse \(0\) als \(12\) interpretiert wird:
$$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$$
Betrachte das Spielzeugbeispiel mit den Koordinaten \(\{0,1,2,3,4\}^2\) und zwei Rechtecken:
$$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$$
In halboffener Schreibweise werden daraus
$$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5).$$
Die \(x\)-Ereignisse liegen also bei \(1,2,4,5\). Die Streifen sehen dann so aus:
$$[0,1):\quad L_0=5.$$
$$[1,2):\quad L_1=3,\ L_0=2.$$
$$[2,4):\quad L_2=2,\ L_1=3.$$
$$[4,5):\quad L_1=4,\ L_0=1.$$
Nach Multiplikation mit den Streifenbreiten folgt
$$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$$
$$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$$
$$C_2=2\cdot 2=4.$$
Alle übrigen \(C_r\) sind \(0\), und tatsächlich gilt \(8+13+4=25\), also die gesamte Gittergröße. Die gewichtete Uhrensumme ist
$$12\cdot 8+1\cdot 13+2\cdot 4=117.$$
Dieses Miniaturbeispiel ist exakt dieselbe Rechnung wie im echten Problem, nur mit sehr viel kleineren Koordinaten.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst erzeugen sie die pseudorandome Folge, nehmen jeweils vier Werte als ein Rechteck und ordnen für jedes Rechteck die kleineren und größeren Koordinaten korrekt zu. Daraus entstehen dann zwei Hilfsdatenmengen: eine Liste von \(x\)-Ereignissen und eine sortierte eindeutige Liste von \(y\)-Grenzen für die Koordinatenkompression.
Anschließend baut die Implementierung einen Segmentbaum über den komprimierten \(y\)-Intervallen auf. Jedes Blatt startet vollständig in Restklasse \(0\), weil vor Beginn des Sweeps jede Gitterposition die Anzeige \(12\) hat. Jeder innere Knoten speichert die gesamte \(y\)-Länge in allen 12 Restklassen. Ein Bereichsupdate berechnet die Überdeckungszahlen nicht neu, sondern rotiert einfach diese 12 gespeicherten Summen; dieselbe Rotation wird als Lazy-Markierung für die Nachkommen gespeichert.
Während des Sweeps verarbeitet die Implementierung die Ereignisse in aufsteigender \(x\)-Reihenfolge. Bevor die Ereignisse an der nächsten \(x\)-Koordinate angewendet werden, multipliziert sie die aktuelle Streifenbreite mit den 12 Restklassenlängen an der Wurzel und addiert das Ergebnis zu globalen Zählern. Danach werden alle Start- und End-Ereignisse an dieser \(x\)-Koordinate als Bereichsrotationen auf den betroffenen \(y\)-Intervallen angewendet. Nach dem letzten Ereignis wird noch der Endstreifen bis \(x=M\) aufsummiert.
Zum Schluss wandelt die Implementierung die Restklassenzähler in die verlangte Uhrensumme um: Restklasse \(0\) erhält das Gewicht \(12\), die Restklassen \(1\) bis \(11\) erhalten ihre jeweilige Zahl. Die eingebauten kleinen Kontrollwerte stimmen mit dieser Herleitung überein, einschließlich des trivialen Falls \(t=0\), bei dem die Antwort einfach \(12M^2\) ist.
Das Erzeugen der Rechtecke kostet \(O(t)\) Zeit. Es gibt höchstens \(2t\) Sweep-Ereignisse und höchstens \(2t+2\) verschiedene \(y\)-Grenzen, also kostet das Sortieren \(O(t\log t)\). Jedes Ereignis führt genau ein Bereichsupdate im Segmentbaum in \(O(\log t)\) aus, mit nur einem festen Faktor \(12\) für die Restklassen. Insgesamt erhält man daher die Laufzeit
$$O(t\log t),$$
und den Speicherverbrauch
$$O(t).$$
\(M=50\,515\,093\) ve \(s_0=290797\) olsun. Sözde rastgele dizi
$$s_{n+1}=s_n^2 \bmod M$$
bağıntısıyla üretilir. Verilen \(t\) için değerler dörderli gruplara ayrılır:
$$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$$
Her dörtlü, \(\{0,\dots,M-1\}^2\) ızgarasında eksenlere paralel kapsayıcı bir dikdörtgen tanımlar:
$$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$$
\((x,y)\) noktasını örten dikdörtgen sayısı \(c_t(x,y)\) ise, görünen saat değeri
$$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{diğer durumlarda.} \end{cases}$$
şeklindedir. İstenen toplam
$$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y))$$
olur. \(M^2\approx 2.55\times 10^{15}\) olduğu için her ızgara hücresini tek tek gezmek imkansızdır. Çözüm bunun yerine bütün şeritleri topluca sayar.
Temel gözlem şudur: Son saat değeri, örtüşme sayısının yalnızca \(12\) modundaki kalıntısına bağlıdır. Böylece problem, ham örtüşme sayıları yerine kalıntı sınıfları üzerinde yapılan bir sweep-line hesabına dönüşür.
Tam sayı ızgarasında
$$[x_1,x_2]\times[y_1,y_2]$$
kapsayıcı dikdörtgeni, tam olarak aynı noktaları
$$[x_1,x_2+1)\times[y_1,y_2+1)$$
yarı açık kutusu ile örter. Bu dönüşüm çok kullanışlıdır; çünkü bir dikdörtgen süpürmeye \(x=x_1\) anında girer ve \(x=x_2+1\) anında çıkar. Yani her dikdörtgen şu olayları üretir:
$$\text{giriş olayı }(x_1,[y_1,y_2],+1),\qquad \text{çıkış olayı }(x_2+1,[y_1,y_2],-1).$$
Eğer \(x_2=M-1\) ise, \(x_2+1=M\) artık ızgaranın dışındadır; bu yüzden sweep içinde ayrıca bir çıkış olayı tutulmaz. Ardışık iki olay \(x\)-değeri arasında aktif dikdörtgen kümesi sabittir. Dolayısıyla bu dikey şeritte \(y\) yönündeki kalıntı dağılımı da sabittir.
Örtüşme düzeni \(y\) boyunca yalnızca dikdörtgen sınırlarında değişebilir. Bu yüzden şu kırılma noktalarını toplamak yeterlidir:
$$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$$
Bunları sıralayıp
$$Y_0 \lt Y_1 \lt \dots \lt Y_m$$
elde ettiğimizde, her \([Y_j,Y_{j+1})\) temel aralığı homojen olur: sabit bir \(x\)-şeridinde aktif her dikdörtgen bu aralığın ya tamamını örter ya da hiç örtmez. Böylece tek tek noktaları izlemek yerine sadece
$$\ell_j=Y_{j+1}-Y_j$$
uzunluklarını saklamak yeterli olur.
Segment ağacındaki herhangi bir \(I\) aralığı için
$$L_r(I)=I\text{ içindeki, örtüşme sayısı }r \pmod{12}\text{ olan toplam }y\text{-uzunluğu},\qquad r=0,1,\dots,11$$
tanımını yapalım. Başlangıçta hiçbir dikdörtgen aktif değildir; dolayısıyla her konumun kalıntısı \(0\)'dır. Uzunluğu \(|I|\) olan bir yaprak için
$$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0$$
olur. Bir dikdörtgen bir \(y\)-aralığında devreye girdiğinde, o bölgedeki her noktanın örtüşme sayısı \(1\) artar; yani kalıntılar döngüsel kayar:
$$L_r'(I)=L_{r-1 \bmod 12}(I).$$
Dikdörtgen çıktığında güncelleme \(-1\) olur ve dönüş ters yöne gider:
$$L_r'(I)=L_{r+1 \bmod 12}(I).$$
Daha genel biçimde, \(\Delta\in\{-1,+1\}\) güncellemesi yalnızca
$$L_r'(I)=L_{r-\Delta \bmod 12}(I)$$
şeklindeki bir döndürmedir. Bu nedenle lazy propagation yeterlidir; bekleyen güncelleme sadece 12 bileşenli bir vektörün döngüsel kaymasıdır.
Şimdi
$$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}$$
olsun. Bir sonraki olay \(x=x_{\text{next}}\) konumunda ve mevcut konum \(x=x_{\text{cur}}\) ise, aradaki şerit genişliği
$$w=x_{\text{next}}-x_{\text{cur}}$$
olur. Bu şeridin tamamında segment ağacının kökü zaten güncel \(L_0,\dots,L_{11}\) uzunluklarını biliyordur. O halde
$$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11)$$
eklemesi yapılır. Bütün şeritler toplandıktan sonra, kalıntı \(0\)'ın saat üzerinde \(12\) gösterdiğini hatırlayarak son toplamı elde ederiz:
$$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$$
\(\{0,1,2,3,4\}^2\) koordinatlı küçük bir ızgarada iki dikdörtgen alalım:
$$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$$
Yarı açık gösterimde bunlar
$$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5)$$
olur. Buna göre \(x\)-olayları \(1,2,4,5\) noktalarındadır. Şeritler şu kalıntı dağılımını verir:
$$[0,1):\quad L_0=5.$$
$$[1,2):\quad L_1=3,\ L_0=2.$$
$$[2,4):\quad L_2=2,\ L_1=3.$$
$$[4,5):\quad L_1=4,\ L_0=1.$$
Şerit genişlikleriyle çarpınca
$$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$$
$$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$$
$$C_2=2\cdot 2=4$$
bulunur. Diğer tüm \(C_r\) değerleri \(0\)'dır ve gerçekten \(8+13+4=25\), yani bütün ızgara hücrelerinin sayısıdır. Ağırlıklı saat toplamı
$$12\cdot 8+1\cdot 13+2\cdot 4=117$$
çıkar. Gerçek girişte yapılan hesap tam olarak bunun çok daha büyük bir sürümüdür.
C++, Python ve Java implementasyonları aynı akışı izler. Önce sözde rastgele dizi üretilir, her dört değer bir dikdörtgen olarak alınır ve her dikdörtgenin alt ve üst sınırları sıralanır. Ardından iki yardımcı veri kümesi oluşturulur: \(x\)-olay listesi ve koordinat sıkıştırması için sıralı tekil \(y\)-sınırları.
Sonra implementasyon, sıkıştırılmış \(y\)-aralıkları üzerinde bir segment ağacı kurar. Başlangıçta her yaprak tamamen kalıntı kovası \(0\)'dadır; çünkü sweep başlamadan önce bütün hücreler \(12\) gösterir. Her iç düğüm, 12 kalıntı sınıfının her biri için toplam \(y\)-uzunluğunu saklar. Bir aralık güncellemesi örtüşme sayılarını tek tek yeniden hesaplamaz; sadece bu 12 toplamı döndürür ve aynı döndürmeyi çocuklara daha sonra iletmek üzere lazy etiketi olarak saklar.
Sweep sırasında implementasyon olayları artan \(x\) sırasıyla işler. Bir sonraki \(x\)-koordinatındaki olayları uygulamadan önce, mevcut şerit genişliğini kökte tutulan 12 kalıntı uzunluğu ile çarpar ve bunları küresel sayaçlara ekler. Ardından o \(x\)-koordinatındaki tüm giriş ve çıkış olayları, ilgili \(y\)-aralıklarında döndürme güncellemeleri olarak uygulanır. Son olaydan sonra \(x=M\)'e kadar kalan son şerit de eklenir.
En sonda implementasyon kalıntı sayaçlarını istenen saat toplamına çevirir: kalıntı \(0\) ağırlık \(12\) alır, kalıntılar \(1\) ile \(11\) ise kendi değerleriyle çarpılır. Implementasyonlardaki küçük kontrol sonuçları bu türetimle uyumludur; buna \(t=0\) için trivyal olarak \(12M^2\) elde edilen durum da dahildir.
Dikdörtgenleri üretmek \(O(t)\) zaman alır. En fazla \(2t\) adet sweep olayı ve en fazla \(2t+2\) adet farklı \(y\)-sınırı vardır; dolayısıyla sıralama maliyeti \(O(t\log t)\)'dir. Her olay, segment ağacında \(O(\log t)\) zamanda bir aralık güncellemesi yapar ve kalıntı kovaları için sabit bir \(12\) katsayısı vardır. Sonuç olarak toplam çalışma süresi
$$O(t\log t),$$
bellek kullanımı ise
$$O(t)$$
olur.
Sea \(M=50\,515\,093\) y \(s_0=290797\), con la recurrencia seudoaleatoria
$$s_{n+1}=s_n^2 \bmod M.$$
Para un valor dado de \(t\), los términos se agrupan de cuatro en cuatro:
$$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$$
Cada cuádrupla define un rectángulo inclusivo alineado con los ejes sobre la rejilla \(\{0,\dots,M-1\}^2\):
$$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$$
Si \(c_t(x,y)\) es el número de rectángulos que cubren la posición \((x,y)\), entonces el valor mostrado por el reloj es
$$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{en caso contrario.} \end{cases}$$
Necesitamos calcular
$$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y)).$$
Como \(M^2\approx 2.55\times 10^{15}\), un recorrido celda por celda es inviable. La solución cuenta franjas completas de la rejilla de una sola vez.
La observación central es que el reloj final depende solo del recubrimiento módulo \(12\). Eso permite reemplazar el seguimiento de conteos exactos por un barrido sobre clases de residuos.
En una rejilla entera, el rectángulo inclusivo
$$[x_1,x_2]\times[y_1,y_2]$$
cubre exactamente las mismas posiciones que la caja semiabierta
$$[x_1,x_2+1)\times[y_1,y_2+1).$$
Esta reformulación es la clave: el rectángulo empieza a afectar el barrido en \(x=x_1\) y deja de hacerlo en \(x=x_2+1\). Así, cada rectángulo aporta
$$\text{evento de entrada }(x_1,[y_1,y_2],+1),\qquad \text{evento de salida }(x_2+1,[y_1,y_2],-1).$$
Si \(x_2=M-1\), entonces \(x_2+1=M\) ya queda fuera de la rejilla y no hace falta almacenar un evento de salida interno. Entre dos coordenadas consecutivas de evento, el conjunto de rectángulos activos no cambia, por lo que la distribución de residuos sobre el eje \(y\) también permanece fija.
El patrón de recubrimiento solo puede cambiar a lo largo de \(y\) en las fronteras de los rectángulos. Por eso basta con reunir los puntos de corte
$$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$$
Después de ordenarlos como
$$Y_0 \lt Y_1 \lt \dots \lt Y_m,$$
cada intervalo elemental \([Y_j,Y_{j+1})\) es uniforme: en una franja fija de \(x\), cada rectángulo activo cubre todo ese intervalo o no cubre nada. Por tanto, en vez de seguir posiciones individuales, solo necesitamos la longitud entera
$$\ell_j=Y_{j+1}-Y_j$$
de cada intervalo comprimido.
Para cualquier intervalo \(I\) del árbol de segmentos, definimos
$$L_r(I)=\text{longitud total en }y\text{ dentro de }I\text{ cuyo recubrimiento actual es }r \pmod{12},\qquad r=0,1,\dots,11.$$
Al principio no hay rectángulos activos, así que toda posición tiene residuo \(0\). Por eso una hoja de longitud \(|I|\) empieza con
$$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0.$$
Cuando un rectángulo entra en un rango de \(y\), todos esos puntos aumentan su recubrimiento en \(1\), así que las clases se rotan:
$$L_r'(I)=L_{r-1 \bmod 12}(I).$$
Cuando el rectángulo sale, la actualización es \(-1\), y la rotación va en el sentido contrario:
$$L_r'(I)=L_{r+1 \bmod 12}(I).$$
En general, una actualización por \(\Delta\in\{-1,+1\}\) se escribe simplemente como
$$L_r'(I)=L_{r-\Delta \bmod 12}(I).$$
Por eso la propagación perezosa funciona tan bien: cada actualización pendiente es solo un corrimiento cíclico de un vector de 12 componentes.
Sea
$$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}.$$
Si el siguiente evento está en \(x=x_{\text{next}}\) y la posición actual del barrido es \(x=x_{\text{cur}}\), el ancho de la franja vale
$$w=x_{\text{next}}-x_{\text{cur}}.$$
Durante toda esa franja, la raíz del árbol de segmentos ya conoce las longitudes actuales \(L_0,\dots,L_{11}\). Así que basta con sumar
$$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11).$$
Al terminar todas las franjas, reconstruimos el valor del reloj recordando que el residuo \(0\) se muestra como \(12\):
$$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$$
Tomemos la rejilla de coordenadas \(\{0,1,2,3,4\}^2\) y dos rectángulos:
$$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$$
En forma semiabierta quedan
$$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5).$$
Los eventos en \(x\) aparecen en \(1,2,4,5\). Las franjas son:
$$[0,1):\quad L_0=5.$$
$$[1,2):\quad L_1=3,\ L_0=2.$$
$$[2,4):\quad L_2=2,\ L_1=3.$$
$$[4,5):\quad L_1=4,\ L_0=1.$$
Multiplicando por los anchos de franja obtenemos
$$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$$
$$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$$
$$C_2=2\cdot 2=4.$$
Los demás \(C_r\) son \(0\), y en efecto \(8+13+4=25\), que coincide con el tamaño total de la rejilla. La suma ponderada del reloj es
$$12\cdot 8+1\cdot 13+2\cdot 4=117.$$
Ese pequeño ejemplo reproduce exactamente la lógica del algoritmo real, solo que con coordenadas muchísimo más pequeñas.
Las implementaciones en C++, Python y Java siguen el mismo recorrido. Primero generan la secuencia seudoaleatoria, agrupan cada cuatro valores en un rectángulo y ordenan cada par de coordenadas para obtener sus extremos inferior y superior. A partir de ahí construyen dos conjuntos auxiliares: una lista de eventos en \(x\) y una lista ordenada y sin repeticiones de fronteras en \(y\) para la compresión de coordenadas.
Después, la implementación construye un árbol de segmentos sobre los intervalos comprimidos de \(y\). Cada hoja empieza completamente en el cubo de residuo \(0\), porque antes del barrido toda celda muestra \(12\). Cada nodo interno guarda la longitud total en \(y\) perteneciente a cada una de las 12 clases de residuos. Una actualización de rango no recalcula los conteos de cobertura; simplemente rota esos 12 totales, y la misma rotación se guarda como marca perezosa para los descendientes.
Durante el barrido, la implementación procesa los eventos en orden creciente de \(x\). Antes de aplicar los eventos de la siguiente coordenada, multiplica el ancho de la franja actual por las 12 longitudes de residuos almacenadas en la raíz y añade el resultado a los acumuladores globales. Luego aplica todos los eventos de entrada y salida en esa coordenada como rotaciones de rango sobre los intervalos afectados de \(y\). Tras el último evento, todavía acumula la franja final hasta \(x=M\).
Por último, la implementación transforma los totales por residuo en la suma pedida: al residuo \(0\) le asigna peso \(12\), y a los residuos \(1\) a \(11\) sus propios valores. Las comprobaciones pequeñas incluidas en las implementaciones concuerdan con esta derivación, incluido el caso trivial \(t=0\), donde la respuesta es simplemente \(12M^2\).
Generar los rectángulos cuesta \(O(t)\) tiempo. Hay como máximo \(2t\) eventos del barrido y como máximo \(2t+2\) fronteras distintas en \(y\), de modo que ordenar todo eso cuesta \(O(t\log t)\). Cada evento ejecuta una actualización de rango en el árbol de segmentos en \(O(\log t)\), con un factor constante de \(12\) debido a los cubos de residuos. Por tanto, el tiempo total es
$$O(t\log t),$$
y la memoria utilizada es
$$O(t).$$
设 \(M=50\,515\,093\)，并令 \(s_0=290797\)。伪随机序列满足
$$s_{n+1}=s_n^2 \bmod M.$$
给定 \(t\) 后，把这些值按四个一组分块：
$$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$$
每一组都会在网格 \(\{0,\dots,M-1\}^2\) 上定义一个与坐标轴平行的闭区间矩形：
$$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$$
如果 \((x,y)\) 这个格点被覆盖的次数是 \(c_t(x,y)\)，那么最后显示在钟面上的数字定义为
$$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{否则。} \end{cases}$$
我们要求的是
$$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y)).$$
由于 \(M^2\approx 2.55\times 10^{15}\)，逐格遍历整个网格完全不可行。可行的方法是把大量具有相同状态的位置整批统计，而不是逐点处理。
最关键的事实是：最终钟面显示只取决于覆盖次数对 \(12\) 的余数，而不取决于精确的覆盖次数本身。因此算法不必存储“到底被盖了多少次”，只需要存储“被盖次数在模 \(12\) 下属于哪一类”。
在整数网格上，闭区间矩形
$$[x_1,x_2]\times[y_1,y_2]$$
与半开区间盒子
$$[x_1,x_2+1)\times[y_1,y_2+1)$$
覆盖的整数格点完全相同。这一步非常重要，因为它把“一个矩形覆盖哪些点”改写成“在什么位置进入、在什么位置离开”。于是，每个矩形都可以变成两个 \(x\) 方向事件：
$$\text{进入事件 }(x_1,[y_1,y_2],+1),\qquad \text{离开事件 }(x_2+1,[y_1,y_2],-1).$$
如果 \(x_2=M-1\)，那么 \(x_2+1=M\) 已经在网格右边界之外，因此扫描过程中不必再额外插入内部离开事件。任意两个相邻事件横坐标之间，活跃矩形集合保持不变，所以那整条竖向条带中的覆盖余数分布也保持不变。
沿着 \(y\) 方向，覆盖状态只会在矩形边界处发生变化。因此只需要收集所有可能的断点：
$$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$$
把它们排序去重后记为
$$Y_0 \lt Y_1 \lt \dots \lt Y_m.$$
这样一来，每个基本区间 \([Y_j,Y_{j+1})\) 在任意固定的 \(x\)-条带内都是均匀的：对当前活跃的任意矩形来说，它要么完整覆盖这个区间，要么完全不覆盖。于是我们不需要跟踪单个格点，只需要知道这个压缩后小区间的整数长度
$$\ell_j=Y_{j+1}-Y_j$$
即可。这个长度正好就是该区间包含的 \(y\) 位置数量。
对线段树中的任意区间 \(I\)，定义
$$L_r(I)=I\text{ 内当前覆盖次数 }\equiv r \pmod{12}\text{ 的总 }y\text{ 长度},\qquad r=0,1,\dots,11.$$
初始时还没有任何矩形被加入，所以所有位置的覆盖次数都是 \(0\)，也就是余数 \(0\)。因此长度为 \(|I|\) 的叶子节点初始状态为
$$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0.$$
当某个矩形在一段 \(y\) 区间上开始生效时，该区间内所有位置的覆盖次数都加 \(1\)，于是余数整体循环右移：
$$L_r'(I)=L_{r-1 \bmod 12}(I).$$
当矩形失效时，更新量是 \(-1\)，循环方向相反：
$$L_r'(I)=L_{r+1 \bmod 12}(I).$$
更一般地，若更新量为 \(\Delta\in\{-1,+1\}\)，则统一写成
$$L_r'(I)=L_{r-\Delta \bmod 12}(I).$$
这说明区间更新根本不需要重新统计精确覆盖次数，只要把 12 个桶做循环旋转即可。正因为如此，懒标记的内容也非常简单，它只是“还需要再旋转多少格”。
定义最终的余数统计量
$$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}.$$
假设当前扫描位置是 \(x=x_{\text{cur}}\)，下一个事件出现在 \(x=x_{\text{next}}\)，那么中间这条竖向条带的宽度为
$$w=x_{\text{next}}-x_{\text{cur}}.$$
在这整个宽度内，活跃矩形集合没有变化，因此线段树根节点给出的 \(L_0,\dots,L_{11}\) 也没有变化。于是可以直接把这条条带的贡献加到全局统计中：
$$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11).$$
扫描完成以后，就得到了每个余数类对应的格点总数。最后因为钟面把余数 \(0\) 显示成 \(12\)，总答案为
$$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$$
考虑坐标集合为 \(\{0,1,2,3,4\}^2\) 的小网格，并取两个矩形
$$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$$
把它们改写成半开形式后得到
$$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5).$$
对应的 \(x\) 事件发生在 \(1,2,4,5\)。于是四条竖向条带上的余数长度分布分别是：
$$[0,1):\quad L_0=5.$$
$$[1,2):\quad L_1=3,\ L_0=2.$$
$$[2,4):\quad L_2=2,\ L_1=3.$$
$$[4,5):\quad L_1=4,\ L_0=1.$$
再乘上各自的条带宽度，就得到
$$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$$
$$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$$
$$C_2=2\cdot 2=4.$$
其余 \(C_r\) 全为 \(0\)。并且 \(8+13+4=25\)，恰好等于整个 \(5\times 5\) 网格的格点总数。于是加权后的钟面总和是
$$12\cdot 8+1\cdot 13+2\cdot 4=117.$$
这正好说明了真实算法在做什么：它并不关心每一个点，而是一次处理整条“状态相同”的区域。
C++、Python 和 Java 实现采用的是同一条处理流水线。首先生成伪随机序列，把每四个数解释成一个矩形，并将每对坐标整理成较小端点和较大端点。接着构造两份派生数据：一份是按 \(x\) 排序的事件列表，另一份是用于 \(y\) 轴坐标压缩的有序去重点集合。
然后，程序在压缩后的 \(y\) 区间上建立一棵线段树。每个叶子节点一开始全部落在余数桶 \(0\) 中，因为在扫描开始前所有格点的覆盖次数都是 \(0\)，钟面都显示 \(12\)。每个内部节点保存 12 个数，表示该节点覆盖范围内分别有多少 \(y\)-长度对应于余数 \(0,1,\dots,11\)。区间更新并不会重新计算覆盖次数，而只是把这 12 个数做一次循环旋转，并把同样的旋转量作为懒标记延迟下传。
扫描过程中，程序按 \(x\) 从小到大处理所有事件。在应用下一个事件坐标上的更新之前，先用当前条带宽度乘上线段树根节点存储的 12 个余数长度，把结果加到全局统计 \(C_0,\dots,C_{11}\) 中。随后，再把该 \(x\) 坐标处的所有进入事件和离开事件作为区间旋转更新到对应的 \(y\) 范围上。最后一个事件之后，还要把剩余直到 \(x=M\) 的那一条尾部条带累加进去。
最终，程序按照钟面的规则把这些余数统计转换成答案：余数 \(0\) 按权重 \(12\) 计入，余数 \(1\) 到 \(11\) 则按自身数值计入。实现中包含的小规模校验与这一推导完全一致，其中也包括最简单的 \(t=0\) 情形，此时答案就是 \(12M^2\)。
生成矩形需要 \(O(t)\) 时间。扫描事件最多有 \(2t\) 个，\(y\) 断点最多有 \(2t+2\) 个，因此排序开销是 \(O(t\log t)\)。每个事件在线段树上做一次区间更新，复杂度为 \(O(\log t)\)，而每个节点只维护固定的 12 个余数桶，所以常数因子也是固定的。于是总时间复杂度为
$$O(t\log t),$$
空间复杂度为
$$O(t).$$
Пусть \(M=50\,515\,093\) и \(s_0=290797\). Псевдослучайная последовательность задается рекуррентно:
$$s_{n+1}=s_n^2 \bmod M.$$
Для заданного \(t\) значения разбиваются на четверки
$$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$$
Каждая четверка задает осесимметричный включительный прямоугольник на сетке \(\{0,\dots,M-1\}^2\):
$$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$$
Если \(c_t(x,y)\) обозначает число прямоугольников, покрывающих позицию \((x,y)\), то отображаемое на циферблате значение равно
$$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{иначе.} \end{cases}$$
Требуется вычислить
$$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y)).$$
Поскольку \(M^2\approx 2.55\times 10^{15}\), полный перебор всех позиций невозможен. Нужно считать сразу большие области, в которых состояние одинаково.
Главное наблюдение состоит в том, что итоговое значение часов зависит только от числа покрытий по модулю \(12\). Значит, вместо точного количества покрытий достаточно хранить лишь его класс вычетов.
На целочисленной сетке прямоугольник
$$[x_1,x_2]\times[y_1,y_2]$$
покрывает те же самые точки, что и полуоткрытый прямоугольник
$$[x_1,x_2+1)\times[y_1,y_2+1).$$
Это делает задачу удобной для сканирующей прямой: прямоугольник начинает действовать в момент \(x=x_1\) и перестает действовать в момент \(x=x_2+1\). Поэтому каждый прямоугольник дает два события:
$$\text{событие входа }(x_1,[y_1,y_2],+1),\qquad \text{событие выхода }(x_2+1,[y_1,y_2],-1).$$
Если \(x_2=M-1\), то \(x_2+1=M\) уже лежит за пределами сетки, поэтому внутреннее событие выхода не нужно. Между двумя соседними координатами событий множество активных прямоугольников постоянно, а значит, постоянно и распределение вычетов вдоль оси \(y\).
Рисунок покрытия по координате \(y\) может меняться только в граничных точках прямоугольников. Поэтому достаточно собрать все точки разбиения
$$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$$
После сортировки и удаления повторов получаем
$$Y_0 \lt Y_1 \lt \dots \lt Y_m.$$
Тогда каждый элементарный интервал \([Y_j,Y_{j+1})\) однороден: в фиксированной полосе по \(x\) любой активный прямоугольник либо покрывает его целиком, либо не покрывает вовсе. Значит, вместо отдельных точек достаточно хранить длину
$$\ell_j=Y_{j+1}-Y_j$$
каждого сжатого интервала.
Для любого интервала \(I\) в дереве отрезков определим
$$L_r(I)=\text{суммарная длина по }y\text{ внутри }I\text{ с текущим покрытием }r \pmod{12},\qquad r=0,1,\dots,11.$$
Изначально ни один прямоугольник не активен, поэтому везде вычет равен \(0\). Для листа длины \(|I|\) имеем
$$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0.$$
Когда прямоугольник начинает действовать на некотором диапазоне по \(y\), все покрытия там увеличиваются на \(1\), и вычеты циклически сдвигаются:
$$L_r'(I)=L_{r-1 \bmod 12}(I).$$
Когда прямоугольник заканчивается, обновление равно \(-1\), и сдвиг идет в обратную сторону:
$$L_r'(I)=L_{r+1 \bmod 12}(I).$$
В общем виде обновление на \(\Delta\in\{-1,+1\}\) записывается как
$$L_r'(I)=L_{r-\Delta \bmod 12}(I).$$
Именно поэтому здесь естественно работает lazy propagation: отложенное обновление сводится к циклическому повороту 12-компонентного вектора.
Пусть
$$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}.$$
Если текущая позиция sweep-line равна \(x=x_{\text{cur}}\), а следующее событие находится в \(x=x_{\text{next}}\), то ширина полосы равна
$$w=x_{\text{next}}-x_{\text{cur}}.$$
На всей этой полосе корень дерева отрезков уже хранит текущие длины \(L_0,\dots,L_{11}\). Значит, можно просто сделать прибавление
$$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11).$$
После обработки всех полос итоговая сумма восстанавливается с учетом того, что вычет \(0\) отображается как \(12\):
$$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$$
Возьмем игрушечную сетку \(\{0,1,2,3,4\}^2\) и два прямоугольника
$$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$$
В полуоткрытой записи это
$$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5).$$
События по \(x\) происходят в точках \(1,2,4,5\). Тогда распределения по полосам таковы:
$$[0,1):\quad L_0=5.$$
$$[1,2):\quad L_1=3,\ L_0=2.$$
$$[2,4):\quad L_2=2,\ L_1=3.$$
$$[4,5):\quad L_1=4,\ L_0=1.$$
Умножая на ширины полос, получаем
$$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$$
$$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$$
$$C_2=2\cdot 2=4.$$
Все остальные \(C_r\) равны нулю, и действительно \(8+13+4=25\), то есть размер всей сетки. Взвешенная сумма часов равна
$$12\cdot 8+1\cdot 13+2\cdot 4=117.$$
Этот небольшой пример в точности иллюстрирует то, что делает алгоритм на реальном входе, только в гигантском масштабе.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала они генерируют псевдослучайную последовательность, собирают каждые четыре значения в один прямоугольник и переставляют координаты так, чтобы нижняя и верхняя границы были записаны в правильном порядке. Затем строятся две производные структуры: список событий по \(x\) и отсортированный набор уникальных границ по \(y\) для сжатия координат.
После этого реализация строит дерево отрезков по сжатым интервалам \(y\). Каждый лист изначально целиком лежит в корзине вычета \(0\), потому что до начала sweep-line у всех клеток покрытие равно нулю, а на часах это соответствует числу \(12\). Каждый внутренний узел хранит суммарную длину по \(y\) для каждой из 12 классов вычетов. Обновление диапазона не пересчитывает покрытия явно; оно просто циклически поворачивает эти 12 накопленных длин и сохраняет такой же поворот как lazy-метку для потомков.
Во время прохода по событиям программа идет по \(x\) слева направо. Перед применением всех событий в следующей координате она умножает текущую ширину полосы на 12 длин вычетов, которые лежат в корне дерева, и добавляет это к глобальным счетчикам. Затем все события входа и выхода в этой координате применяются как диапазонные повороты на затронутых отрезках по \(y\). После последнего события отдельно добавляется хвостовая полоса до \(x=M\).
В конце реализация переводит накопленные значения \(C_0,\dots,C_{11}\) в требуемую сумму: вычет \(0\) получает вес \(12\), а вычеты \(1\)–\(11\) получают свои собственные веса. Малые контрольные значения, присутствующие в реализациях, полностью согласуются с этим выводом, включая тривиальный случай \(t=0\), где ответ равен \(12M^2\).
Построение прямоугольников занимает \(O(t)\) времени. Событий sweep-line не больше \(2t\), различных границ по \(y\) не больше \(2t+2\), так что сортировка требует \(O(t\log t)\). Каждое событие выполняет одно диапазонное обновление дерева отрезков за \(O(\log t)\), причем размер набора вычетов фиксирован и равен \(12\). Следовательно, полная асимптотика такова:
$$O(t\log t)$$
по времени и
$$O(t)$$
по памяти.
لنفرض أن \(M=50\,515\,093\) وأن \(s_0=290797\). تُولَّد المتتالية شبه العشوائية بالعلاقة
$$s_{n+1}=s_n^2 \bmod M.$$
ولقيمة معطاة \(t\)، نأخذ القيم على شكل رباعيات:
$$\left(a_i,b_i,c_i,d_i\right)=\left(s_{4i},s_{4i+1},s_{4i+2},s_{4i+3}\right),\qquad 0\le i\lt t.$$
كل رباعية تعرّف مستطيلاً شاملاً موازياً للمحورين على الشبكة \(\{0,\dots,M-1\}^2\):
$$R_i=[\min(a_i,b_i),\max(a_i,b_i)]\times[\min(c_i,d_i),\max(c_i,d_i)].$$
إذا كانت \(c_t(x,y)\) هي عدد المستطيلات التي تغطي الموضع \((x,y)\)، فإن القيمة الظاهرة على الساعة هي
$$\phi(c)=\begin{cases} 12, & c\equiv 0 \pmod{12},\\ c \bmod 12, & \text{في غير ذلك.} \end{cases}$$
والمطلوب هو حساب
$$A(t)=\sum_{x=0}^{M-1}\sum_{y=0}^{M-1}\phi(c_t(x,y)).$$
ولأن \(M^2\approx 2.55\times 10^{15}\)، فإن المرور على كل خلية في الشبكة مباشرةً غير ممكن عملياً. لذلك تعتمد الفكرة على عدّ أشرطة كاملة دفعة واحدة بدل التعامل مع الخلايا منفردة.
الملاحظة الأساسية هي أن القيمة النهائية على الساعة لا تعتمد إلا على عدد مرات التغطية modulo \(12\). لهذا السبب لا نحتاج إلى تخزين عدد التغطيات بدقة، بل يكفي أن نعرف فئة الباقي التي ينتمي إليها.
على شبكة صحيحة، فإن المستطيل الشامل
$$[x_1,x_2]\times[y_1,y_2]$$
يغطي النقاط الصحيحة نفسها تماماً التي يغطيها الصندوق نصف المفتوح
$$[x_1,x_2+1)\times[y_1,y_2+1).$$
هذه الصياغة مفيدة جداً لأنها تجعل كل مستطيل يدخل في المسح عند \(x=x_1\) ويخرج عند \(x=x_2+1\). لذلك يعطي كل مستطيل حدثين:
$$\text{حدث دخول }(x_1,[y_1,y_2],+1),\qquad \text{حدث خروج }(x_2+1,[y_1,y_2],-1).$$
إذا كان \(x_2=M-1\)، فإن \(x_2+1=M\) يقع مباشرةً خارج حدود الشبكة، ولذلك لا حاجة إلى حدث خروج داخلي. وبين أي قيمتين متتاليتين للأحداث على محور \(x\)، تبقى مجموعة المستطيلات الفعالة ثابتة، وبالتالي يبقى توزيع البواقي على محور \(y\) ثابتاً أيضاً.
لا يمكن لنمط التغطية على محور \(y\) أن يتغير إلا عند حدود المستطيلات. ولهذا يكفي جمع نقاط الانكسار التالية:
$$0,\ M,\ y_1^{(i)},\ y_2^{(i)}+1.$$
وبعد ترتيبها وحذف التكرارات نحصل على
$$Y_0 \lt Y_1 \lt \dots \lt Y_m.$$
حينئذ يكون كل مجال أساسي \([Y_j,Y_{j+1})\) متجانساً: ففي شريط \(x\) ثابت، كل مستطيل فعّال إما أن يغطي هذا المجال كله أو يتركه كله. لذلك لا نحتاج إلى متابعة كل خلية على حدة، بل يكفي أن نعرف طول المجال المضغوط
$$\ell_j=Y_{j+1}-Y_j.$$
لكل مجال \(I\) في شجرة المقاطع نعرّف
$$L_r(I)=\text{إجمالي طول }y\text{ داخل }I\text{ الذي يملك حالياً تغطية }r \pmod{12},\qquad r=0,1,\dots,11.$$
في البداية لا يوجد أي مستطيل فعّال، لذا فكل المواضع تملك الباقي \(0\). ومن ثم فإن الورقة ذات الطول \(|I|\) تبدأ بالحالة
$$L_0(I)=|I|,\qquad L_1(I)=\dots=L_{11}(I)=0.$$
عندما يبدأ تأثير مستطيل على مجال من \(y\)، تزداد التغطية بمقدار \(1\) في جميع تلك المواضع، وبالتالي تدور فئات البواقي دوراناً دورياً:
$$L_r'(I)=L_{r-1 \bmod 12}(I).$$
وعندما ينتهي تأثير المستطيل تكون التحديثات \(-1\)، فيحدث الدوران في الاتجاه المعاكس:
$$L_r'(I)=L_{r+1 \bmod 12}(I).$$
وبصورة عامة، إذا كانت قيمة التحديث \(\Delta\in\{-1,+1\}\)، فإن القاعدة الموحدة هي
$$L_r'(I)=L_{r-\Delta \bmod 12}(I).$$
وهذا يفسر لماذا تكفي خاصية التأجيل في شجرة المقاطع: فالتحديث المؤجل ليس إلا تدويراً دورياً لمتجه ذي 12 خانة.
لنعرّف
$$C_r=\#\left\{(x,y)\in\{0,\dots,M-1\}^2:\ c_t(x,y)\equiv r \pmod{12}\right\}.$$
إذا كان موضع المسح الحالي هو \(x=x_{\text{cur}}\) وكان الحدث التالي عند \(x=x_{\text{next}}\)، فإن عرض الشريط بينهما يساوي
$$w=x_{\text{next}}-x_{\text{cur}}.$$
طوال هذا الشريط تبقى مجموعة المستطيلات الفعالة ثابتة، وبالتالي تبقى القيم \(L_0,\dots,L_{11}\) في جذر الشجرة ثابتة أيضاً. لذلك يمكننا ببساطة إجراء التحديث
$$C_r \leftarrow C_r + w\,L_r\qquad (r=0,\dots,11).$$
وبعد الانتهاء من كل الأشرطة نستعيد المجموع النهائي مع تذكّر أن الباقي \(0\) يُعرض على الساعة بوصفه \(12\):
$$A(t)=12C_0+\sum_{r=1}^{11} r\,C_r.$$
لنأخذ شبكة إحداثياتها \(\{0,1,2,3,4\}^2\) ومستطيلين هما
$$R_1=[1,3]\times[0,2],\qquad R_2=[2,4]\times[1,4].$$
بعد تحويلهما إلى صيغة نصف مفتوحة نحصل على
$$R_1=[1,4)\times[0,3),\qquad R_2=[2,5)\times[1,5).$$
تظهر أحداث \(x\) عند القيم \(1,2,4,5\). وعندئذ تكون توزيعات الأطوال حسب البواقي على الأشرطة كما يلي:
$$[0,1):\quad L_0=5.$$
$$[1,2):\quad L_1=3,\ L_0=2.$$
$$[2,4):\quad L_2=2,\ L_1=3.$$
$$[4,5):\quad L_1=4,\ L_0=1.$$
وبضربها في عروض الأشرطة نحصل على
$$C_0=5\cdot 1+2\cdot 1+1\cdot 1=8,$$
$$C_1=3\cdot 1+3\cdot 2+4\cdot 1=13,$$
$$C_2=2\cdot 2=4.$$
وجميع القيم الأخرى \(C_r\) تساوي صفراً، كما أن \(8+13+4=25\) وهو عدد خلايا الشبكة كلها. ومن ثم يكون مجموع الساعة الموزون
$$12\cdot 8+1\cdot 13+2\cdot 4=117.$$
هذا المثال الصغير يطابق تماماً ما تفعله الخوارزمية الحقيقية، لكنه يعمل على مدى إحداثيات صغير يسهل تتبعه يدوياً.
تتبع تطبيقات C++ وPython وJava المسار نفسه. فهي تبدأ بتوليد المتتالية شبه العشوائية، ثم تجمع كل أربعة أعداد في مستطيل واحد، ثم ترتب كل زوج من الإحداثيات للحصول على الحد الأدنى والحد الأقصى الصحيحين. بعد ذلك تُنشئ بنيتين مشتقتين: قائمة بأحداث \(x\)، وقائمة مرتبة وفريدة بحدود \(y\) اللازمة لضغط الإحداثيات.
بعدها تُبنى شجرة مقاطع فوق المجالات المضغوطة على محور \(y\). كل ورقة تبدأ بكامل طولها داخل سلة الباقي \(0\)، لأن أي خلية قبل بدء المسح لها تغطية صفرية، وبالتالي تعرض الساعة الرقم \(12\). وكل عقدة داخلية تحتفظ بإجمالي طول \(y\) الموافق لكل واحدة من فئات البواقي الاثنتي عشرة. وعند تحديث مجال ما لا تعيد الشيفرة حساب التغطيات صراحةً، بل تكتفي بتدوير هذه المجاميع الاثني عشر، ثم تحفظ مقدار التدوير نفسه كوسم مؤجل للأبناء.
أثناء المسح، تعالج الشيفرة الأحداث بترتيب تصاعدي في \(x\). وقبل تطبيق الأحداث الواقعة عند الإحداثي التالي، تضرب عرض الشريط الحالي في أطوال البواقي الاثني عشر الموجودة في جذر الشجرة، ثم تضيف النتيجة إلى العدادات العالمية. وبعد ذلك تطبق جميع أحداث الدخول والخروج عند ذلك الإحداثي على شكل تدويرات مجال على المقاطع المناسبة من محور \(y\). وبعد آخر حدث، ما زال هناك شريط أخير حتى \(x=M\) يجب جمعه أيضاً.
وفي النهاية تحوّل الشيفرة مجاميع البواقي إلى الجواب المطلوب: فالباقي \(0\) يُعطى الوزن \(12\)، أما البواقي من \(1\) إلى \(11\) فتُضرب في قيمها نفسها. كما أن قيم التحقق الصغيرة الموجودة في التطبيقات تتفق تماماً مع هذا الاشتقاق، بما في ذلك الحالة البديهية \(t=0\) حيث يكون الجواب \(12M^2\).
توليد المستطيلات يحتاج إلى زمن \(O(t)\). ولدينا بحد أقصى \(2t\) من أحداث المسح، وبحد أقصى \(2t+2\) من حدود \(y\) المختلفة، لذلك تكون كلفة الفرز \(O(t\log t)\). وكل حدث ينفذ تحديث مجال واحداً في شجرة المقاطع بكلفة \(O(\log t)\)، مع عامل ثابت صغير لأن عدد سلال البواقي ثابت ويساوي \(12\). وبالتالي يكون التعقيد الزمني الكلي
$$O(t\log t),$$
بينما يكون استهلاك الذاكرة
$$O(t).$$