Problem 212 asks for the volume of the union of \(N=50000\) axis-aligned cuboids. The cuboids are generated deterministically from a lagged Fibonacci sequence, so the input is large but completely fixed. Each cuboid has the half-open form
$$C_i=[x_i,x_i+d_{x,i})\times[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}),$$
with \(x_i,y_i,z_i\in\{0,\dots,9999\}\) and \(1\le d_{x,i},d_{y,i},d_{z,i}\le 399\).
The challenge is the overlap structure: \(50000\) cuboids can intersect in extremely complicated ways, so direct inclusion-exclusion is useless. The successful approach is to exploit the arithmetic structure of the coordinates. Because all coordinates are integers and every \(x\)-length is at most \(399\), the entire 3D problem can be reduced to about \(10^4\) independent 2D union-area problems.
The pseudo-random sequence is
$$S_k=(100003-200003k+300007k^3)\bmod 10^6\qquad(1\le k\le 55),$$
followed by the recurrence
$$S_k=(S_{k-24}+S_{k-55})\bmod 10^6\qquad(k\ge 56).$$
Every cuboid uses six consecutive values:
$$x_i=S_{6i-5}\bmod 10000,\qquad y_i=S_{6i-4}\bmod 10000,\qquad z_i=S_{6i-3}\bmod 10000,$$
$$d_{x,i}=1+(S_{6i-2}\bmod 399),\qquad d_{y,i}=1+(S_{6i-1}\bmod 399),\qquad d_{z,i}=1+(S_{6i}\bmod 399).$$
The half-open convention matters. If two cuboids only touch on a face or an edge, that boundary has zero volume and is not double-counted. It also means that every unit box \([x,x+1)\times[y,y+1)\times[z,z+1)\) is either fully inside the union or fully outside it.
Let
$$X_{\max}=\max_i(x_i+d_{x,i}).$$
For each integer \(x\in\{0,1,\dots,X_{\max}-1\}\), consider the slab \([x,x+1)\). Inside that slab, a cuboid contributes exactly when \(x_i\le x<x_i+d_{x,i}\), and then its cross-section is the rectangle
$$[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}).$$
If we denote by \(A_x\) the union area of all such active rectangles, then the full volume is exactly
$$V=\sum_{x=0}^{X_{\max}-1} A_x,$$
where
$$A_x=\operatorname{area}\!\Bigg(\bigcup_{i:\,x_i\le x<x_i+d_{x,i}}[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i})\Bigg).$$
This is not an approximation. The slab thickness is 1, the active set is constant throughout the slab, and the coordinates are integral, so summing the cross-sectional areas gives the exact 3D volume.
Fix one slab. Suppose its active rectangles are
$$R_j=[a_j,b_j)\times[c_j,d_j)\qquad(1\le j\le m).$$
We sweep upward in the \(y\)-direction. Each rectangle generates two events:
$$ (a_j,\,[c_j,d_j),\,+1),\qquad (b_j,\,[c_j,d_j),\,-1). $$
Between two consecutive event heights, the active set of rectangles does not change, so the covered length on the \(z\)-axis is constant there. If that covered \(z\)-length is \(L_z\) on the strip from \(y=u\) to \(y=v\), then the strip contributes
$$L_z\,(v-u)$$
to the slab area. Summing over all strips gives \(A_x\).
The only dynamic quantity during the sweep is the union length of the active \(z\)-intervals. The implementations maintain a segment tree over the integer \(z\)-range \([0,Z_{\max})\), where
$$Z_{\max}=\max_i(z_i+d_{z,i}).$$
For every node interval \(I=[\ell,r)\), the tree stores a cover count \(c(I)\) and a covered length \(\lambda(I)\). The invariant is
$$\lambda(I)= \begin{cases} r-\ell, & c(I)>0,\\ 0, & c(I)=0\text{ and }r-\ell=1,\\ \lambda(I_{\mathrm{left}})+\lambda(I_{\mathrm{right}}), & c(I)=0\text{ and }r-\ell>1. \end{cases}$$
If a node is covered by at least one active rectangle, its whole interval is covered. Otherwise, coverage is determined entirely by its children. Therefore the root always stores the current union length on the \(z\)-axis, exactly the quantity needed for the sweep formula.
Take two cuboids
$$C_1=[0,2)\times[0,3)\times[0,1),\qquad C_2=[1,3)\times[1,4)\times[0,2).$$
They occupy the slabs \(x=0,1,2\).
For \(x=0\), only \(C_1\) is active, so \(A_0=3\cdot 1=3\).
For \(x=1\), both are active. The two rectangles in the \((y,z)\)-plane are
$$[0,3)\times[0,1),\qquad [1,4)\times[0,2).$$
The event heights are \(0,1,3,4\). The covered \(z\)-length is \(1\) on \([0,1)\), then \(2\) on \([1,3)\), then still \(2\) on \([3,4)\). Hence
$$A_1=1\cdot(1-0)+2\cdot(3-1)+2\cdot(4-3)=7.$$
For \(x=2\), only \(C_2\) is active, so \(A_2=3\cdot 2=6\). Therefore
$$V=A_0+A_1+A_2=3+7+6=16.$$
This miniature example is exactly the same geometry as the full problem: turn volume into slab areas, then turn each slab area into a sweep over rectangle events.
The C++, Python, and Java implementations first generate the first \(6N\) sequence values and convert them into \(50000\) half-open cuboids. The C++ and Java versions then use a difference-array pass over the \(x\)-axis to count how many rectangles will be active in each slab, so they can reserve or allocate exact per-slab storage. The Python version directly appends rectangles into slab lists, but it builds the same mathematical object: for each integer \(x\), the full list of \((y,z)\)-rectangles that appear in the slab \([x,x+1)\).
Each slab is processed independently. The implementation builds \(2R_x\) events for a slab with \(R_x\) active rectangles, sorts them by \(y\), and sweeps upward while updating a segment tree on the raw \(z\)-coordinate range. No coordinate compression is needed here because the generated coordinates never exceed roughly \(10^4\), so the direct tree is already small enough. After every gap in the sorted event list, the current covered \(z\)-length at the root is multiplied by the height of the gap and added to the slab area.
Once the slab areas are available, they are simply summed to obtain the final volume. The C++ implementation distributes slabs dynamically across worker threads and reuses one sweep structure per worker. The Python implementation splits the \(x\)-range into blocks and evaluates those blocks in separate worker processes. The Java implementation performs the same slab-by-slab sweep serially. The C++ solution also contains internal validation against small brute-force tests and against the known \(100\)-cuboid checkpoint before running the full instance.
Let \(R_x\) be the number of active rectangles in slab \(x\), and define
$$M=\sum_x R_x=\sum_{i=1}^{N} d_{x,i}.$$
Because every \(x\)-length satisfies \(d_{x,i}\le 399\), we have the concrete bound \(M\le 399N\). Building the cuboids is \(O(N)\), and materializing all slab lists is \(O(M)\) time and \(O(M)\) memory.
For each slab, the code sorts \(2R_x\) events and performs \(2R_x\) segment-tree updates. This gives total running time
$$O\!\left(\sum_x R_x\log R_x + M\log Z_{\max}\right),$$
with \(Z_{\max}\le 10398\). The additional working memory for one sweep structure is \(O(Z_{\max})\), so the full memory footprint is \(O(M+WZ_{\max})\) if \(W\) workers are used. In practice this is efficient precisely because the problem's coordinate bounds are small enough to justify explicit slab storage.
Problem 212 verlangt das Volumen der Vereinigung von \(N=50000\) achsenparallelen Quadern. Die Quader werden nicht direkt angegeben, sondern deterministisch aus einer Lagged-Fibonacci-Folge erzeugt. Jeder Quader hat die halboffene Form
$$C_i=[x_i,x_i+d_{x,i})\times[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}),$$
wobei \(x_i,y_i,z_i\in\{0,\dots,9999\}\) und \(1\le d_{x,i},d_{y,i},d_{z,i}\le 399\) gilt.
Schwierig ist nicht ein einzelner Quader, sondern die komplizierte Überlappung von \(50000\) Quadern. Inklusions-Exklusions-Formeln sind hier unbrauchbar. Die erfolgreiche Idee nutzt stattdessen zwei spezielle Eigenschaften dieser Instanz: Alle Koordinaten sind ganzzahlig, und jede \(x\)-Ausdehnung ist höchstens \(399\). Dadurch kann man das 3D-Problem in ungefähr \(10^4\) unabhängige 2D-Vereinigungsprobleme zerlegen.
Die pseudozufällige Folge lautet
$$S_k=(100003-200003k+300007k^3)\bmod 10^6\qquad(1\le k\le 55),$$
und anschließend
$$S_k=(S_{k-24}+S_{k-55})\bmod 10^6\qquad(k\ge 56).$$
Je sechs aufeinanderfolgende Werte bestimmen einen Quader:
$$x_i=S_{6i-5}\bmod 10000,\qquad y_i=S_{6i-4}\bmod 10000,\qquad z_i=S_{6i-3}\bmod 10000,$$
$$d_{x,i}=1+(S_{6i-2}\bmod 399),\qquad d_{y,i}=1+(S_{6i-1}\bmod 399),\qquad d_{z,i}=1+(S_{6i}\bmod 399).$$
Die halboffene Schreibweise ist wichtig. Wenn sich zwei Quader nur an einer Fläche oder Kante berühren, entsteht kein doppelt gezähltes Volumen. Außerdem ist jedes Einheitskästchen \([x,x+1)\times[y,y+1)\times[z,z+1)\) eindeutig entweder innerhalb oder außerhalb der Vereinigung.
Setze
$$X_{\max}=\max_i(x_i+d_{x,i}).$$
Für jedes ganze \(x\in\{0,1,\dots,X_{\max}-1\}\) betrachten wir die Scheibe \([x,x+1)\). Ein Quader trägt dort genau dann bei, wenn \(x_i\le x<x_i+d_{x,i}\), und sein Schnitt ist dann das Rechteck
$$[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}).$$
Bezeichnen wir mit \(A_x\) die Vereinigungsfläche aller in dieser Scheibe aktiven Rechtecke, so gilt exakt
$$V=\sum_{x=0}^{X_{\max}-1} A_x,$$
wobei
$$A_x=\operatorname{area}\!\Bigg(\bigcup_{i:\,x_i\le x<x_i+d_{x,i}}[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i})\Bigg).$$
Das ist keine Näherung. Die Scheibendicke ist 1, die aktive Quaderliste ändert sich innerhalb einer Scheibe nicht, und wegen der ganzzahligen Koordinaten ergibt die Summe der Schnittflächen genau das gesamte Volumen.
Fixiere eine Scheibe. Ihre aktiven Rechtecke seien
$$R_j=[a_j,b_j)\times[c_j,d_j)\qquad(1\le j\le m).$$
Nun wird in \(y\)-Richtung gesweept. Jedes Rechteck erzeugt zwei Ereignisse:
$$ (a_j,\,[c_j,d_j),\,+1),\qquad (b_j,\,[c_j,d_j),\,-1). $$
Zwischen zwei aufeinanderfolgenden Ereignishöhen ändert sich die aktive Rechteckmenge nicht, also bleibt die überdeckte Länge auf der \(z\)-Achse konstant. Wenn diese überdeckte Länge auf dem Streifen von \(y=u\) bis \(y=v\) gleich \(L_z\) ist, dann liefert der Streifen den Flächenbeitrag
$$L_z\,(v-u).$$
Die Summe über alle Streifen ergibt \(A_x\).
Während des Sweeps ist die einzige dynamische Größe die Vereinigungslänge der aktiven \(z\)-Intervalle. Die Implementierungen verwalten dafür einen Segmentbaum über dem ganzzahligen Bereich \([0,Z_{\max})\), wobei
$$Z_{\max}=\max_i(z_i+d_{z,i}).$$
Für jedes Knotenintervall \(I=[\ell,r)\) speichert der Baum eine Überdeckungszahl \(c(I)\) und eine überdeckte Länge \(\lambda(I)\). Die Invariante lautet
$$\lambda(I)= \begin{cases} r-\ell, & c(I)>0,\\ 0, & c(I)=0\text{ und }r-\ell=1,\\ \lambda(I_{\mathrm{links}})+\lambda(I_{\mathrm{rechts}}), & c(I)=0\text{ und }r-\ell>1. \end{cases}$$
Sobald ein Knotenintervall von mindestens einem aktiven Rechteck vollständig bedeckt wird, ist seine ganze Länge bedeckt. Nur wenn die Überdeckungszahl null ist, muss man auf die Kinder schauen. Deshalb enthält die Wurzel jederzeit exakt die aktuelle Vereinigungslänge auf der \(z\)-Achse.
Betrachte die beiden Quader
$$C_1=[0,2)\times[0,3)\times[0,1),\qquad C_2=[1,3)\times[1,4)\times[0,2).$$
Sie belegen die Scheiben \(x=0,1,2\).
Für \(x=0\) ist nur \(C_1\) aktiv, also \(A_0=3\cdot 1=3\).
Für \(x=1\) sind beide aktiv. In der \((y,z)\)-Ebene liegen dann die Rechtecke
$$[0,3)\times[0,1),\qquad [1,4)\times[0,2).$$
Die Ereignishöhen sind \(0,1,3,4\). Die überdeckte \(z\)-Länge ist \(1\) auf \([0,1)\), dann \(2\) auf \([1,3)\) und schließlich noch \(2\) auf \([3,4)\). Also
$$A_1=1\cdot(1-0)+2\cdot(3-1)+2\cdot(4-3)=7.$$
Für \(x=2\) bleibt nur \(C_2\), also \(A_2=3\cdot 2=6\). Damit ist
$$V=A_0+A_1+A_2=3+7+6=16.$$
Dieses kleine Beispiel verwendet genau dieselbe Geometrie wie die Vollversion: Volumen wird zu Scheibenflächen, und jede Scheibenfläche wird durch einen Sweep über Rechteckereignisse berechnet.
Die Implementierungen in C++, Python und Java erzeugen zunächst die ersten \(6N\) Folgenterme und wandeln sie in \(50000\) halboffene Quader um. Die C++- und Java-Versionen machen anschließend einen Difference-Array-Durchlauf über die \(x\)-Achse, um für jede Scheibe die Anzahl aktiver Rechtecke zu kennen und dadurch den Speicher exakt zu reservieren. Die Python-Version hängt die Rechtecke direkt an Listen an, baut aber dasselbe mathematische Objekt auf: für jedes ganze \(x\) die vollständige Liste aller \((y,z)\)-Rechtecke in der Scheibe \([x,x+1)\).
Jede Scheibe wird unabhängig verarbeitet. Für eine Scheibe mit \(R_x\) aktiven Rechtecken werden \(2R_x\) Ereignisse erzeugt, nach \(y\) sortiert und dann mit einem Segmentbaum über dem unveränderten \(z\)-Koordinatenbereich abgearbeitet. Eine Koordinatenkompression ist hier nicht nötig, weil die erzeugten Werte nur bis knapp über \(10^4\) reichen. Nach jeder Lücke in der sortierten Ereignisliste wird die momentan an der Wurzel gespeicherte überdeckte \(z\)-Länge mit der Höhe der Lücke multipliziert und zur Scheibenfläche addiert.
Sind alle Scheibenflächen bekannt, werden sie einfach summiert. Die C++-Version verteilt Scheiben dynamisch auf Worker-Threads und verwendet pro Worker eine wiederverwendbare Sweep-Struktur. Die Python-Version zerlegt den \(x\)-Bereich in Blöcke und berechnet diese Blöcke in separaten Prozessen. Die Java-Version führt denselben Scheiben-Sweep seriell aus. Zusätzlich enthält die C++-Lösung interne Validierungen gegen kleine Brute-Force-Beispiele und gegen den bekannten Zwischenwert für die ersten \(100\) Quader.
Sei \(R_x\) die Anzahl aktiver Rechtecke in der Scheibe \(x\), und definiere
$$M=\sum_x R_x=\sum_{i=1}^{N} d_{x,i}.$$
Wegen \(d_{x,i}\le 399\) gilt konkret \(M\le 399N\). Das Erzeugen der Quader kostet \(O(N)\), und das Materialisieren aller Scheibenlisten kostet \(O(M)\) Zeit und \(O(M)\) Speicher.
In jeder Scheibe werden \(2R_x\) Ereignisse sortiert und \(2R_x\) Segmentbaum-Updates durchgeführt. Insgesamt ergibt sich somit
$$O\!\left(\sum_x R_x\log R_x + M\log Z_{\max}\right),$$
wobei \(Z_{\max}\le 10398\) gilt. Der zusätzliche Arbeitsspeicher für eine Sweep-Struktur ist \(O(Z_{\max})\), also insgesamt \(O(M+WZ_{\max})\), wenn \(W\) Worker verwendet werden. Praktisch ist das Verfahren schnell, weil die Koordinatenbeschränkungen klein genug sind, um explizite Scheibenlisten zu rechtfertigen.
Problem 212, \(N=50000\) adet eksenlere paralel dikdörtgenler prizmasının birleşim hacmini sorar. Prizmalar doğrudan verilmez; tüm koordinatlar ve kenar uzunlukları deterministik bir gecikmeli Fibonacci dizisinden üretilir. Her prizma şu yarı-açık biçimdedir:
$$C_i=[x_i,x_i+d_{x,i})\times[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}),$$
burada \(x_i,y_i,z_i\in\{0,\dots,9999\}\) ve \(1\le d_{x,i},d_{y,i},d_{z,i}\le 399\).
Zorluk tek bir prizmanın hacmi değil, \(50000\) prizmanın oluşturduğu karmaşık örtüşme yapısıdır. Dahil et-dışla yaklaşımı burada işe yaramaz. Başarılı çözüm, bu örneğin iki özel yönünü kullanır: tüm koordinatlar tam sayıdır ve her \(x\)-uzunluğu en fazla \(399\) olur. Böylece tüm 3B problem yaklaşık \(10^4\) adet bağımsız 2B birleşim alanı problemine indirgenir.
Sözde rastgele dizi
$$S_k=(100003-200003k+300007k^3)\bmod 10^6\qquad(1\le k\le 55),$$
ve ardından
$$S_k=(S_{k-24}+S_{k-55})\bmod 10^6\qquad(k\ge 56)$$
şeklindedir. Her prizma art arda gelen altı terimden kurulur:
$$x_i=S_{6i-5}\bmod 10000,\qquad y_i=S_{6i-4}\bmod 10000,\qquad z_i=S_{6i-3}\bmod 10000,$$
$$d_{x,i}=1+(S_{6i-2}\bmod 399),\qquad d_{y,i}=1+(S_{6i-1}\bmod 399),\qquad d_{z,i}=1+(S_{6i}\bmod 399).$$
Yarı-açık gösterim önemlidir. İki prizma yalnızca bir yüz veya kenar üzerinde temas ediyorsa, bu sınırın hacmi sıfırdır ve çift sayım oluşmaz. Ayrıca her birim hücre \([x,x+1)\times[y,y+1)\times[z,z+1)\) birleşimin ya tamamen içindedir ya da tamamen dışındadır.
Şunu tanımlayalım:
$$X_{\max}=\max_i(x_i+d_{x,i}).$$
Her tam sayı \(x\in\{0,1,\dots,X_{\max}-1\}\) için \([x,x+1)\) dilimini ele alalım. Bir prizma bu dilime tam olarak \(x_i\le x<x_i+d_{x,i}\) iken katkı yapar ve bu durumda kesiti şu dikdörtgendir:
$$[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}).$$
Bu dilimde aktif olan tüm dikdörtgenlerin birleşim alanını \(A_x\) ile gösterirsek toplam hacim tam olarak
$$V=\sum_{x=0}^{X_{\max}-1} A_x,$$
olur; burada
$$A_x=\operatorname{area}\!\Bigg(\bigcup_{i:\,x_i\le x<x_i+d_{x,i}}[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i})\Bigg).$$
Bu bir yaklaşık hesap değil, tam eşitliktir. Dilim kalınlığı 1'dir, dilim boyunca aktif prizma kümesi değişmez ve tüm koordinatlar tam sayı olduğundan kesit alanlarını toplamak 3B hacmi eksiksiz verir.
Şimdi tek bir dilimi sabitleyelim. O dilimde aktif olan dikdörtgenler
$$R_j=[a_j,b_j)\times[c_j,d_j)\qquad(1\le j\le m)$$
olsun. \(y\) yönünde bir süpürme yapılır. Her dikdörtgen iki olay üretir:
$$ (a_j,\,[c_j,d_j),\,+1),\qquad (b_j,\,[c_j,d_j),\,-1). $$
Ardışık iki olay yüksekliği arasında aktif dikdörtgen kümesi değişmez; dolayısıyla \(z\)-eksenindeki kaplı uzunluk sabittir. Eğer \(y=u\) ile \(y=v\) arasındaki şeritte bu kaplı uzunluk \(L_z\) ise, o şeridin alana katkısı
$$L_z\,(v-u)$$
olur. Tüm şeritler toplanınca \(A_x\) elde edilir.
Süpürme sırasında dinamik olarak değişen tek nicelik, aktif \(z\)-aralıklarının birleşim uzunluğudur. Uygulamalar bunun için \([0,Z_{\max})\) tam sayı aralığı üzerinde bir segment ağacı tutar; burada
$$Z_{\max}=\max_i(z_i+d_{z,i}).$$
Her düğüm aralığı \(I=[\ell,r)\) için ağaç bir örtü sayısı \(c(I)\) ve kaplı uzunluk \(\lambda(I)\) saklar. Değişmez şu şekildedir:
$$\lambda(I)= \begin{cases} r-\ell, & c(I)>0,\\ 0, & c(I)=0\text{ ve }r-\ell=1,\\ \lambda(I_{\mathrm{sol}})+\lambda(I_{\mathrm{sag}}), & c(I)=0\text{ ve }r-\ell>1. \end{cases}$$
Bir düğüm aralığı en az bir aktif dikdörtgen tarafından tamamen örtülüyorsa tüm uzunluğu kaplıdır. Yalnızca örtü sayısı sıfırsa çocuklara inmek gerekir. Bu nedenle kök düğüm her anda \(z\)-eksenindeki güncel birleşim uzunluğunu verir; süpürme formülünde gereken nicelik tam olarak budur.
Şu iki prizmayı alalım:
$$C_1=[0,2)\times[0,3)\times[0,1),\qquad C_2=[1,3)\times[1,4)\times[0,2).$$
Bunlar \(x=0,1,2\) dilimlerini kaplar.
\(x=0\) için yalnızca \(C_1\) aktiftir, dolayısıyla \(A_0=3\cdot 1=3\).
\(x=1\) için ikisi de aktiftir. \((y,z)\)-düzlemindeki iki dikdörtgen
$$[0,3)\times[0,1),\qquad [1,4)\times[0,2)$$
olur. Olay yükseklikleri \(0,1,3,4\) değerleridir. Kaplı \(z\)-uzunluğu \([0,1)\) üzerinde \(1\), \([1,3)\) üzerinde \(2\), \([3,4)\) üzerinde yine \(2\) olur. Bu yüzden
$$A_1=1\cdot(1-0)+2\cdot(3-1)+2\cdot(4-3)=7.$$
\(x=2\) için yalnızca \(C_2\) kaldığından \(A_2=3\cdot 2=6\). Sonuçta
$$V=A_0+A_1+A_2=3+7+6=16$$
elde edilir. Bu küçük örnek, tam problemde kullanılan geometriyi bire bir gösterir: hacim, dilim alanlarına; her dilim alanı da olaylar üzerinden yapılan bir dikdörtgen süpürmesine dönüşür.
C++, Python ve Java uygulamaları önce ilk \(6N\) dizi terimini üretir ve bunlardan \(50000\) yarı-açık prizma oluşturur. C++ ve Java sürümleri daha sonra \(x\)-ekseni üzerinde bir fark dizisi geçişi yaparak her dilimde kaç aktif dikdörtgen olacağını önceden sayar; böylece dilim depolarını tam boyutta ayırabilirler. Python sürümü doğrudan listelere ekleme yapar, ancak o da aynı matematiksel nesneyi kurar: her tam sayı \(x\) için \([x,x+1)\) diliminde görünen tüm \((y,z)\)-dikdörtgenlerinin listesi.
Her dilim bağımsız işlenir. Bir dilimde \(R_x\) aktif dikdörtgen varsa \(2R_x\) olay üretilir, bunlar \(y\)'ye göre sıralanır ve ham \(z\)-koordinat aralığı üzerinde bir segment ağacı ile işlenir. Üretilen koordinatlar yaklaşık \(10^4\) düzeyini aşmadığı için burada koordinat sıkıştırmasına ihtiyaç yoktur. Sıralı olay listesindeki her boşlukta, kökte tutulan güncel \(z\)-birleşim uzunluğu o boşluğun yüksekliğiyle çarpılır ve dilim alanına eklenir.
Tüm dilim alanları hesaplandıktan sonra bunlar toplanarak son hacim bulunur. C++ uygulaması dilimleri iş parçacıklarına dinamik olarak dağıtır ve her işçi için bir süpürme yapısını yeniden kullanır. Python uygulaması \(x\)-aralığını bloklara ayırıp bu blokları ayrı süreçlerde hesaplar. Java uygulaması aynı dilim süpürmesini tek iş parçacığında yürütür. C++ çözümünde ayrıca küçük kaba kuvvet testleri ve ilk \(100\) prizma için bilinen ara değerle doğrulama da bulunur.
\(x\) dilimindeki aktif dikdörtgen sayısı \(R_x\) olsun ve
$$M=\sum_x R_x=\sum_{i=1}^{N} d_{x,i}$$
tanımlansın. Her \(d_{x,i}\le 399\) olduğundan somut olarak \(M\le 399N\) sınırı vardır. Prizmaları üretmek \(O(N)\), tüm dilim listelerini kurmak ise \(O(M)\) zaman ve \(O(M)\) bellek gerektirir.
Her dilimde \(2R_x\) olay sıralanır ve \(2R_x\) segment ağacı güncellemesi yapılır. Toplam çalışma süresi bu yüzden
$$O\!\left(\sum_x R_x\log R_x + M\log Z_{\max}\right)$$
olur; burada \(Z_{\max}\le 10398\). Tek bir süpürme yapısının ek belleği \(O(Z_{\max})\) olduğundan, \(W\) işçi kullanıldığında toplam bellek \(O(M+WZ_{\max})\) düzeyindedir. Uygulamada bu yöntem hızlıdır; çünkü problemdeki koordinat sınırları açık dilim listeleri tutmayı mümkün kılar.
El problema 212 pide el volumen de la unión de \(N=50000\) cuboides alineados con los ejes. Los cuboides no se dan de forma explícita: sus coordenadas iniciales y sus longitudes salen de una sucesión determinista de tipo lagged Fibonacci. Cada cuboide tiene la forma semiabierta
$$C_i=[x_i,x_i+d_{x,i})\times[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}),$$
con \(x_i,y_i,z_i\in\{0,\dots,9999\}\) y \(1\le d_{x,i},d_{y,i},d_{z,i}\le 399\).
La dificultad real es la superposición entre \(50000\) cuboides. La inclusión-exclusión es inviable, y un algoritmo 3D completamente general sería más complicado de lo que hace falta aquí. La clave es aprovechar dos rasgos concretos de esta instancia: todas las coordenadas son enteras y toda longitud en el eje \(x\) es como mucho \(399\). Eso permite reemplazar el problema espacial por unas \(10^4\) uniones de rectángulos en dos dimensiones.
La sucesión pseudoaleatoria es
$$S_k=(100003-200003k+300007k^3)\bmod 10^6\qquad(1\le k\le 55),$$
seguida por la recurrencia
$$S_k=(S_{k-24}+S_{k-55})\bmod 10^6\qquad(k\ge 56).$$
Cada cuboide usa seis términos consecutivos:
$$x_i=S_{6i-5}\bmod 10000,\qquad y_i=S_{6i-4}\bmod 10000,\qquad z_i=S_{6i-3}\bmod 10000,$$
$$d_{x,i}=1+(S_{6i-2}\bmod 399),\qquad d_{y,i}=1+(S_{6i-1}\bmod 399),\qquad d_{z,i}=1+(S_{6i}\bmod 399).$$
La convención semiabierta es importante. Si dos cuboides solo se tocan en una cara o en una arista, esa frontera tiene volumen cero y no crea doble conteo. Además, toda caja unidad \([x,x+1)\times[y,y+1)\times[z,z+1)\) queda inequívocamente dentro o fuera de la unión.
Definimos
$$X_{\max}=\max_i(x_i+d_{x,i}).$$
Para cada entero \(x\in\{0,1,\dots,X_{\max}-1\}\), miramos la lámina \([x,x+1)\). Un cuboide contribuye a esa lámina exactamente cuando \(x_i\le x<x_i+d_{x,i}\), y en ese caso su sección es el rectángulo
$$[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}).$$
Si \(A_x\) denota el área de la unión de todos los rectángulos activos en esa lámina, entonces el volumen total es
$$V=\sum_{x=0}^{X_{\max}-1} A_x,$$
donde
$$A_x=\operatorname{area}\!\Bigg(\bigcup_{i:\,x_i\le x<x_i+d_{x,i}}[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i})\Bigg).$$
No se trata de una aproximación. El grosor de la lámina es 1, el conjunto activo no cambia dentro de la lámina y las coordenadas son enteras, de modo que sumar áreas de secciones produce exactamente el volumen 3D.
Fijemos una lámina. Sus rectángulos activos son
$$R_j=[a_j,b_j)\times[c_j,d_j)\qquad(1\le j\le m).$$
Se hace un barrido creciente en \(y\). Cada rectángulo produce dos eventos:
$$ (a_j,\,[c_j,d_j),\,+1),\qquad (b_j,\,[c_j,d_j),\,-1). $$
Entre dos alturas consecutivas de evento, el conjunto de rectángulos activos no cambia, así que la longitud cubierta sobre el eje \(z\) permanece constante. Si esa longitud cubierta es \(L_z\) en la franja \(y\in[u,v)\), la contribución de esa franja al área es
$$L_z\,(v-u).$$
La suma de todas esas franjas da \(A_x\).
Durante el barrido, la única cantidad dinámica es la longitud de la unión de los intervalos activos en \(z\). Las implementaciones mantienen un árbol de segmentos sobre el rango entero \([0,Z_{\max})\), con
$$Z_{\max}=\max_i(z_i+d_{z,i}).$$
Para cada intervalo de nodo \(I=[\ell,r)\), el árbol guarda un contador de cobertura \(c(I)\) y una longitud cubierta \(\lambda(I)\). La invariante es
$$\lambda(I)= \begin{cases} r-\ell, & c(I)>0,\\ 0, & c(I)=0\text{ y }r-\ell=1,\\ \lambda(I_{\mathrm{izq}})+\lambda(I_{\mathrm{der}}), & c(I)=0\text{ y }r-\ell>1. \end{cases}$$
Si al menos un rectángulo activo cubre completamente el intervalo del nodo, toda su longitud cuenta. Solo cuando el contador es cero hace falta mirar a los hijos. Por eso la raíz contiene en todo momento la longitud de unión actual sobre \(z\), exactamente la magnitud necesaria para el barrido.
Tomemos los cuboides
$$C_1=[0,2)\times[0,3)\times[0,1),\qquad C_2=[1,3)\times[1,4)\times[0,2).$$
Ocupan las láminas \(x=0,1,2\).
Para \(x=0\), solo está activo \(C_1\), así que \(A_0=3\cdot 1=3\).
Para \(x=1\), están activos ambos. En el plano \((y,z)\) aparecen los rectángulos
$$[0,3)\times[0,1),\qquad [1,4)\times[0,2).$$
Las alturas de evento son \(0,1,3,4\). La longitud cubierta en \(z\) vale \(1\) sobre \([0,1)\), luego \(2\) sobre \([1,3)\) y sigue siendo \(2\) sobre \([3,4)\). Entonces
$$A_1=1\cdot(1-0)+2\cdot(3-1)+2\cdot(4-3)=7.$$
Para \(x=2\), queda solo \(C_2\), así que \(A_2=3\cdot 2=6\). Por tanto
$$V=A_0+A_1+A_2=3+7+6=16.$$
Este ejemplo pequeño ilustra exactamente la misma geometría que la instancia completa: convertir volumen en áreas por lámina y cada una de esas áreas en un barrido por eventos de rectángulos.
Las implementaciones en C++, Python y Java generan primero los \(6N\) términos de la sucesión y los convierten en \(50000\) cuboides semiabiertos. Las versiones en C++ y Java hacen luego una pasada con arreglo de diferencias sobre el eje \(x\) para saber cuántos rectángulos estarán activos en cada lámina y así reservar memoria exacta por lámina. La versión en Python añade directamente a listas, pero construye el mismo objeto matemático: para cada entero \(x\), la lista completa de rectángulos \((y,z)\) presentes en \([x,x+1)\).
Cada lámina se procesa de manera independiente. La implementación crea \(2R_x\) eventos para una lámina con \(R_x\) rectángulos activos, los ordena por \(y\) y hace el barrido actualizando un árbol de segmentos sobre el rango bruto de coordenadas \(z\). No hace falta compresión de coordenadas porque los valores generados nunca pasan de un rango de tamaño cercano a \(10^4\). Después de cada hueco en la lista ordenada de eventos, la longitud cubierta actual en la raíz se multiplica por la altura del hueco y se suma al área de la lámina.
Una vez obtenidas todas las áreas, solo queda sumarlas. La implementación en C++ reparte las láminas dinámicamente entre varios hilos y reutiliza una estructura de barrido por trabajador. La implementación en Python divide el rango de \(x\) en bloques y evalúa esos bloques en procesos separados. La implementación en Java hace el mismo barrido lámina por lámina de forma serial. La versión en C++ también incluye validaciones internas contra casos pequeños por fuerza bruta y contra el valor conocido para los primeros \(100\) cuboides.
Sea \(R_x\) el número de rectángulos activos en la lámina \(x\), y definamos
$$M=\sum_x R_x=\sum_{i=1}^{N} d_{x,i}.$$
Como siempre se cumple \(d_{x,i}\le 399\), tenemos el límite concreto \(M\le 399N\). Generar los cuboides cuesta \(O(N)\), y materializar todas las listas de láminas cuesta \(O(M)\) tiempo y \(O(M)\) memoria.
En cada lámina se ordenan \(2R_x\) eventos y se realizan \(2R_x\) actualizaciones del árbol de segmentos. El tiempo total es entonces
$$O\!\left(\sum_x R_x\log R_x + M\log Z_{\max}\right),$$
con \(Z_{\max}\le 10398\). La memoria adicional de una estructura de barrido es \(O(Z_{\max})\), de modo que el consumo total es \(O(M+WZ_{\max})\) si se usan \(W\) trabajadores. En la práctica este enfoque funciona bien precisamente porque las cotas numéricas del problema permiten almacenar explícitamente las láminas.
第 212 题要求计算 \(N=50000\) 个轴对齐长方体并集的体积。这些长方体并不是直接给出的，而是由一个确定性的滞后斐波那契序列生成。每个长方体都写成半开区间形式
$$C_i=[x_i,x_i+d_{x,i})\times[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}),$$
其中 \(x_i,y_i,z_i\in\{0,\dots,9999\}\)，而 \(1\le d_{x,i},d_{y,i},d_{z,i}\le 399\)。
真正困难的地方不在于单个长方体，而在于 \(50000\) 个长方体之间极其复杂的重叠关系。容斥法根本无法展开，一个完全通用的三维并集算法对这里来说又没有必要。代码抓住了这道题的两个关键特征：坐标全是整数，而且每个长方体在 \(x\) 方向上的长度最多只有 \(399\)。正因为如此，整个三维体积问题可以被精确地拆成大约 \(10^4\) 个相互独立的二维矩形并面积问题。
伪随机序列的前 \(55\) 项由
$$S_k=(100003-200003k+300007k^3)\bmod 10^6\qquad(1\le k\le 55)$$
给出，之后满足递推
$$S_k=(S_{k-24}+S_{k-55})\bmod 10^6\qquad(k\ge 56).$$
第 \(i\) 个长方体使用连续的六个序列值：
$$x_i=S_{6i-5}\bmod 10000,\qquad y_i=S_{6i-4}\bmod 10000,\qquad z_i=S_{6i-3}\bmod 10000,$$
$$d_{x,i}=1+(S_{6i-2}\bmod 399),\qquad d_{y,i}=1+(S_{6i-1}\bmod 399),\qquad d_{z,i}=1+(S_{6i}\bmod 399).$$
半开区间写法非常关键。如果两个长方体只是共享一个面或者一条棱，那部分边界的体积为零，不会重复计数。更重要的是，每个单位小盒子 \([x,x+1)\times[y,y+1)\times[z,z+1)\) 都会被明确地判定为“在并集内”或“在并集外”。
记
$$X_{\max}=\max_i(x_i+d_{x,i}).$$
对每个整数 \(x\in\{0,1,\dots,X_{\max}-1\}\)，考虑厚度为 1 的薄层 \([x,x+1)\)。某个长方体在这一层中出现，当且仅当 \(x_i\le x<x_i+d_{x,i}\)。此时它在 \((y,z)\) 平面中的截面就是矩形
$$[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}).$$
把这一层所有活动矩形的并面积记为 \(A_x\)，那么总并集体积恰好等于
$$V=\sum_{x=0}^{X_{\max}-1} A_x,$$
其中
$$A_x=\operatorname{area}\!\Bigg(\bigcup_{i:\,x_i\le x<x_i+d_{x,i}}[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i})\Bigg).$$
这里没有任何数值近似。因为薄层厚度固定为 1，层内活动长方体集合不变，而且所有坐标都是整数，所以把每层的截面积直接相加，就是完整而精确的三维体积。
固定某个 \(x\)-薄层。设这一层中的活动矩形为
$$R_j=[a_j,b_j)\times[c_j,d_j)\qquad(1\le j\le m).$$
接着在 \(y\) 方向做扫描线。每个矩形贡献两个事件：
$$ (a_j,\,[c_j,d_j),\,+1),\qquad (b_j,\,[c_j,d_j),\,-1). $$
在相邻两个事件高度之间，活动矩形集合不发生变化，因此 \(z\) 轴上的被覆盖总长度保持不变。若在区间 \(y\in[u,v)\) 上，这个覆盖长度为 \(L_z\)，那么这一条水平带对面积的贡献就是
$$L_z\,(v-u).$$
把所有这样的水平带累加起来，就得到该薄层的并面积 \(A_x\)。
扫描过程中唯一动态变化的量，是当前所有活动 \(z\)-区间并集的长度。实现方法是在整数范围 \([0,Z_{\max})\) 上维护一棵线段树，其中
$$Z_{\max}=\max_i(z_i+d_{z,i}).$$
对每个节点区间 \(I=[\ell,r)\)，线段树记录两个量：覆盖计数 \(c(I)\) 和已覆盖长度 \(\lambda(I)\)。不变量是
$$\lambda(I)= \begin{cases} r-\ell, & c(I)>0,\\ 0, & c(I)=0\text{ 且 }r-\ell=1,\\ \lambda(I_{\mathrm{left}})+\lambda(I_{\mathrm{right}}), & c(I)=0\text{ 且 }r-\ell>1. \end{cases}$$
也就是说，只要某个节点区间被至少一个活动矩形完整覆盖，它的覆盖长度就是整个区间长度；只有当覆盖计数为零时，才需要看左右孩子的和。因此根节点在任意时刻保存的，正是扫描线当前所需要的 \(z\) 轴并长度。
考虑两个长方体
$$C_1=[0,2)\times[0,3)\times[0,1),\qquad C_2=[1,3)\times[1,4)\times[0,2).$$
它们会出现在 \(x=0,1,2\) 这三层。
当 \(x=0\) 时，只有 \(C_1\) 活动，所以 \(A_0=3\cdot 1=3\)。
当 \(x=1\) 时，二者都活动，此时 \((y,z)\) 平面中的两个矩形是
$$[0,3)\times[0,1),\qquad [1,4)\times[0,2).$$
事件高度依次为 \(0,1,3,4\)。在 \([0,1)\) 上，\(z\) 覆盖长度是 \(1\)；在 \([1,3)\) 上变为 \(2\)；在 \([3,4)\) 上仍然是 \(2\)。因此
$$A_1=1\cdot(1-0)+2\cdot(3-1)+2\cdot(4-3)=7.$$
当 \(x=2\) 时，只剩 \(C_2\)，所以 \(A_2=3\cdot 2=6\)。于是总并体积为
$$V=A_0+A_1+A_2=3+7+6=16.$$
这个小例子已经完整展示了正式算法的结构：先把体积分解成薄层面积，再把每一层面积写成一次扫描线问题。
C++、Python 和 Java 三个实现都会先生成前 \(6N\) 个序列值，再把它们转成 \(50000\) 个半开长方体。C++ 和 Java 版本随后会在 \(x\) 轴上先做一遍差分计数，算出每个薄层里会有多少个活动矩形，从而为每个薄层预留恰当的存储空间。Python 版本直接向列表追加，但构造出的数学对象完全相同：对每个整数 \(x\)，保存薄层 \([x,x+1)\) 中全部 \((y,z)\) 矩形。
每个薄层都是独立处理的。对于某层的 \(R_x\) 个活动矩形，程序构造 \(2R_x\) 个事件，按 \(y\) 排序，然后在原始 \(z\) 坐标范围上维护线段树并向上扫描。这里不需要坐标压缩，因为生成出来的坐标上界本来就只有一万出头。每当有一段相邻事件之间的空隙，程序就用根节点保存的当前 \(z\) 覆盖长度乘上这段空隙的高度，并把结果加到该层面积中。
所有薄层面积求完后，直接相加就是最终体积。C++ 实现把薄层动态分发给多个工作线程，并为每个线程复用一套扫描结构。Python 实现把 \(x\) 轴范围切成若干块，交给多个工作进程计算。Java 实现则按照同样的数学流程串行处理所有薄层。C++ 版本还额外带有若干内部校验，包括小规模暴力比对以及前 \(100\) 个长方体的已知检查值。
设薄层 \(x\) 中的活动矩形数为 \(R_x\)，并定义
$$M=\sum_x R_x=\sum_{i=1}^{N} d_{x,i}.$$
由于每个 \(d_{x,i}\le 399\)，所以有明确上界 \(M\le 399N\)。生成全部长方体的代价是 \(O(N)\)，把它们展开到所有 \(x\)-薄层中的代价是 \(O(M)\) 时间和 \(O(M)\) 内存。
对每个薄层，需要排序 \(2R_x\) 个事件，并执行 \(2R_x\) 次线段树更新，因此总时间复杂度为
$$O\!\left(\sum_x R_x\log R_x + M\log Z_{\max}\right),$$
其中 \(Z_{\max}\le 10398\)。单套扫描结构的额外空间是 \(O(Z_{\max})\)，所以如果使用 \(W\) 个工作器，总空间可写成 \(O(M+WZ_{\max})\)。在这道题里，这个方法之所以实用，正是因为坐标范围足够小，可以直接把薄层显式存下来。
В задаче 212 требуется найти объем объединения \(N=50000\) прямоугольных параллелепипедов, ориентированных вдоль координатных осей. Эти параллелепипеды не даны напрямую: их начальные координаты и длины ребер порождаются детерминированной lagged-Fibonacci-последовательностью. Каждый параллелепипед имеет полууоткрытый вид
$$C_i=[x_i,x_i+d_{x,i})\times[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}),$$
где \(x_i,y_i,z_i\in\{0,\dots,9999\}\), а \(1\le d_{x,i},d_{y,i},d_{z,i}\le 399\).
Основная трудность связана не с отдельным телом, а с крайне сложной структурой перекрытий между \(50000\) телами. Включение-исключение здесь бесполезно, а полностью общий 3D-алгоритм был бы излишне тяжелым. Реальное решение использует две специальные особенности этой задачи: все координаты целые, а длина по оси \(x\) никогда не превосходит \(399\). Благодаря этому трехмерную задачу можно точно разложить примерно на \(10^4\) независимых двумерных задач об объединении прямоугольников.
Псевдослучайная последовательность задается так:
$$S_k=(100003-200003k+300007k^3)\bmod 10^6\qquad(1\le k\le 55),$$
а затем выполняется рекуррентное соотношение
$$S_k=(S_{k-24}+S_{k-55})\bmod 10^6\qquad(k\ge 56).$$
Каждый параллелепипед строится по шести последовательным значениям:
$$x_i=S_{6i-5}\bmod 10000,\qquad y_i=S_{6i-4}\bmod 10000,\qquad z_i=S_{6i-3}\bmod 10000,$$
$$d_{x,i}=1+(S_{6i-2}\bmod 399),\qquad d_{y,i}=1+(S_{6i-1}\bmod 399),\qquad d_{z,i}=1+(S_{6i}\bmod 399).$$
Полууоткрытая запись важна. Если два тела лишь соприкасаются гранью или ребром, эта граница имеет нулевой объем и не дает двойного счета. Кроме того, каждый единичный блок \([x,x+1)\times[y,y+1)\times[z,z+1)\) однозначно либо принадлежит объединению, либо нет.
Обозначим
$$X_{\max}=\max_i(x_i+d_{x,i}).$$
Для каждого целого \(x\in\{0,1,\dots,X_{\max}-1\}\) рассмотрим слой \([x,x+1)\). Параллелепипед участвует в этом слое тогда и только тогда, когда \(x_i\le x<x_i+d_{x,i}\). Его сечение в слое есть прямоугольник
$$[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}).$$
Если через \(A_x\) обозначить площадь объединения всех прямоугольников, активных в данном слое, то полный объем равен
$$V=\sum_{x=0}^{X_{\max}-1} A_x,$$
где
$$A_x=\operatorname{area}\!\Bigg(\bigcup_{i:\,x_i\le x<x_i+d_{x,i}}[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i})\Bigg).$$
Это точное равенство, а не приближение. Толщина слоя равна 1, набор активных тел внутри слоя не меняется, а все координаты целые, поэтому сумма площадей сечений в точности совпадает с искомым объемом.
Зафиксируем один слой. Пусть его активные прямоугольники равны
$$R_j=[a_j,b_j)\times[c_j,d_j)\qquad(1\le j\le m).$$
Далее выполняется sweep-line по оси \(y\). Каждый прямоугольник создает два события:
$$ (a_j,\,[c_j,d_j),\,+1),\qquad (b_j,\,[c_j,d_j),\,-1). $$
Между двумя соседними уровнями событий набор активных прямоугольников не меняется, значит, суммарная покрытая длина по оси \(z\) остается постоянной. Если на полосе \(y\in[u,v)\) эта длина равна \(L_z\), то вклад полосы в площадь равен
$$L_z\,(v-u).$$
Сумма по всем таким полосам дает площадь \(A_x\).
Во время sweep-line динамически меняется только длина объединения активных интервалов по \(z\). Для этого реализации поддерживают дерево отрезков на целочисленном диапазоне \([0,Z_{\max})\), где
$$Z_{\max}=\max_i(z_i+d_{z,i}).$$
Для каждого узлового интервала \(I=[\ell,r)\) хранятся счетчик покрытия \(c(I)\) и покрытая длина \(\lambda(I)\). Инвариант имеет вид
$$\lambda(I)= \begin{cases} r-\ell, & c(I)>0,\\ 0, & c(I)=0\text{ и }r-\ell=1,\\ \lambda(I_{\mathrm{left}})+\lambda(I_{\mathrm{right}}), & c(I)=0\text{ и }r-\ell>1. \end{cases}$$
Если интервал узла полностью покрыт хотя бы одним активным прямоугольником, то его покрытая длина равна полной длине интервала. Лишь когда счетчик покрытия равен нулю, нужно суммировать информацию из детей. Поэтому корень дерева в любой момент времени содержит текущую длину объединения по оси \(z\).
Рассмотрим два параллелепипеда
$$C_1=[0,2)\times[0,3)\times[0,1),\qquad C_2=[1,3)\times[1,4)\times[0,2).$$
Они занимают слои \(x=0,1,2\).
Для \(x=0\) активен только \(C_1\), поэтому \(A_0=3\cdot 1=3\).
Для \(x=1\) активны оба. В плоскости \((y,z)\) получаем прямоугольники
$$[0,3)\times[0,1),\qquad [1,4)\times[0,2).$$
Уровни событий равны \(0,1,3,4\). Покрытая длина по \(z\) равна \(1\) на \([0,1)\), затем \(2\) на \([1,3)\), и остается \(2\) на \([3,4)\). Следовательно,
$$A_1=1\cdot(1-0)+2\cdot(3-1)+2\cdot(4-3)=7.$$
Для \(x=2\) остается только \(C_2\), так что \(A_2=3\cdot 2=6\). Значит,
$$V=A_0+A_1+A_2=3+7+6=16.$$
Этот небольшой пример полностью повторяет структуру полного решения: объем раскладывается по слоям, а площадь каждого слоя вычисляется sweep-line-методом.
Реализации на C++, Python и Java сначала строят первые \(6N\) членов последовательности и преобразуют их в \(50000\) полууоткрытых параллелепипедов. Версии на C++ и Java затем делают проход с массивом разностей по оси \(x\), чтобы заранее узнать число активных прямоугольников в каждом слое и выделить память точно нужного размера. Версия на Python сразу добавляет прямоугольники в списки, но строит тот же самый математический объект: для каждого целого \(x\) полный список прямоугольников \((y,z)\), присутствующих в слое \([x,x+1)\).
Каждый слой обрабатывается независимо. Для слоя с \(R_x\) активными прямоугольниками программа создает \(2R_x\) событий, сортирует их по \(y\) и выполняет sweep-line, обновляя дерево отрезков на исходном диапазоне координат \(z\). Сжатие координат здесь не нужно, потому что сами координаты ограничены величиной порядка \(10^4\). После каждого промежутка между соседними уровнями событий текущая длина покрытия в корне умножается на высоту промежутка и добавляется к площади слоя.
Когда площади всех слоев готовы, они просто суммируются. Реализация на C++ распределяет слои динамически между потоками и переиспользует одну sweep-структуру на каждого работника. Реализация на Python разбивает диапазон \(x\) на блоки и вычисляет их в отдельных процессах. Реализация на Java выполняет тот же слоевой sweep-line последовательно. В версии на C++ также встроены проверки на малых brute-force-примерах и на известном контрольном значении для первых \(100\) параллелепипедов.
Пусть \(R_x\) обозначает число активных прямоугольников в слое \(x\), и пусть
$$M=\sum_x R_x=\sum_{i=1}^{N} d_{x,i}.$$
Поскольку всегда \(d_{x,i}\le 399\), имеем конкретную оценку \(M\le 399N\). Построение всех параллелепипедов требует \(O(N)\), а развертывание их по слоям требует \(O(M)\) времени и \(O(M)\) памяти.
В каждом слое сортируются \(2R_x\) событий и выполняются \(2R_x\) обновления дерева отрезков. Поэтому суммарное время равно
$$O\!\left(\sum_x R_x\log R_x + M\log Z_{\max}\right),$$
где \(Z_{\max}\le 10398\). Дополнительная память одной sweep-структуры составляет \(O(Z_{\max})\), так что полный расход памяти можно записать как \(O(M+WZ_{\max})\), если используется \(W\) работников. Метод оказывается практичным именно потому, что числовые границы задачи позволяют хранить слои явно.
تطلب المسألة 212 حساب حجم اتحاد \(N=50000\) متوازي مستطيلات موازية للمحاور. هذه المجسمات لا تُعطى مباشرة، بل تُولَّد حتميًا من متتالية lagged Fibonacci. يكتب كل متوازي مستطيلات على الصورة نصف المفتوحة
$$C_i=[x_i,x_i+d_{x,i})\times[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}),$$
حيث \(x_i,y_i,z_i\in\{0,\dots,9999\}\) و\(1\le d_{x,i},d_{y,i},d_{z,i}\le 399\).
الصعوبة الحقيقية ليست في حجم صندوق واحد، بل في شبكة التداخل المعقدة بين \(50000\) صندوق. مبدأ الشمول والاستبعاد غير عملي هنا، وخوارزمية ثلاثية الأبعاد عامة تمامًا ستكون أعقد من اللازم. الفكرة الناجحة تعتمد على خاصيتين فعليتين في هذه المسألة: جميع الإحداثيات صحيحة، وطول كل صندوق على محور \(x\) لا يزيد على \(399\). لذلك يمكن تحويل المسألة ثلاثية الأبعاد بدقة إلى نحو \(10^4\) مسائل ثنائية الأبعاد مستقلة لحساب مساحة اتحاد مستطيلات.
تعطى المتتالية شبه العشوائية في أول \(55\) حدًا بواسطة
$$S_k=(100003-200003k+300007k^3)\bmod 10^6\qquad(1\le k\le 55),$$
ثم تحقق العلاقة
$$S_k=(S_{k-24}+S_{k-55})\bmod 10^6\qquad(k\ge 56).$$
ويُبنى الصندوق رقم \(i\) من ست قيم متتالية:
$$x_i=S_{6i-5}\bmod 10000,\qquad y_i=S_{6i-4}\bmod 10000,\qquad z_i=S_{6i-3}\bmod 10000,$$
$$d_{x,i}=1+(S_{6i-2}\bmod 399),\qquad d_{y,i}=1+(S_{6i-1}\bmod 399),\qquad d_{z,i}=1+(S_{6i}\bmod 399).$$
الصياغة نصف المفتوحة مهمة جدًا. فإذا تلامس صندوقان في وجه أو حافة فقط، فإن تلك الحدود ذات حجم صفري ولا تؤدي إلى عد مضاعف. كما أن كل خلية وحدة من الشكل \([x,x+1)\times[y,y+1)\times[z,z+1)\) تكون إما داخل الاتحاد بالكامل أو خارجه بالكامل.
لنعرّف
$$X_{\max}=\max_i(x_i+d_{x,i}).$$
لكل عدد صحيح \(x\in\{0,1,\dots,X_{\max}-1\}\) ننظر إلى الشريحة \([x,x+1)\). يساهم الصندوق في هذه الشريحة بالضبط عندما \(x_i\le x<x_i+d_{x,i}\)، وعندئذ يكون مقطعه المستوي هو المستطيل
$$[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i}).$$
إذا رمزنا بمساحة اتحاد جميع المستطيلات الفعالة في هذه الشريحة إلى \(A_x\)، فإن الحجم الكلي يساوي تمامًا
$$V=\sum_{x=0}^{X_{\max}-1} A_x,$$
حيث
$$A_x=\operatorname{area}\!\Bigg(\bigcup_{i:\,x_i\le x<x_i+d_{x,i}}[y_i,y_i+d_{y,i})\times[z_i,z_i+d_{z,i})\Bigg).$$
هذه ليست مقاربة عددية. سمك كل شريحة يساوي 1، ومجموعة الصناديق الفعالة لا تتغير داخل الشريحة، وجميع الإحداثيات صحيحة؛ لذلك فإن جمع مساحات المقاطع يعطي الحجم الثلاثي الأبعاد بدقة تامة.
لنثبت شريحة واحدة. ولتكن المستطيلات الفعالة فيها
$$R_j=[a_j,b_j)\times[c_j,d_j)\qquad(1\le j\le m).$$
نطبق خط مسح تصاعديًا على محور \(y\). كل مستطيل يولد حدثين:
$$ (a_j,\,[c_j,d_j),\,+1),\qquad (b_j,\,[c_j,d_j),\,-1). $$
بين مستويين متتاليين من الأحداث، لا تتغير مجموعة المستطيلات الفعالة، وبالتالي يبقى طول التغطية على محور \(z\) ثابتًا. إذا كان هذا الطول هو \(L_z\) على الشريط \(y\in[u,v)\)، فإن مساهمة ذلك الشريط في المساحة هي
$$L_z\,(v-u).$$
وبجمع مساهمات جميع الأشرطة نحصل على \(A_x\).
الكمية الديناميكية الوحيدة أثناء المسح هي طول اتحاد الفترات الفعالة على محور \(z\). لذلك تحفظ التطبيقات شجرة مقاطع على المجال الصحيح \([0,Z_{\max})\)، حيث
$$Z_{\max}=\max_i(z_i+d_{z,i}).$$
لكل مجال عقدة \(I=[\ell,r)\) نخزن عداد تغطية \(c(I)\) وطولًا مغطى \(\lambda(I)\). والثابت هو
$$\lambda(I)= \begin{cases} r-\ell, & c(I)>0,\\ 0, & c(I)=0\text{ and }r-\ell=1,\\ \lambda(I_{\mathrm{left}})+\lambda(I_{\mathrm{right}}), & c(I)=0\text{ and }r-\ell>1. \end{cases}$$
إذا كان مجال العقدة مغطى بالكامل بواسطة مستطيل فعال واحد على الأقل، فطوله المغطى يساوي طول المجال كله. وعندما يكون عداد التغطية صفرًا فقط نرجع إلى الأبناء. لذلك فإن الجذر يعطي في كل لحظة طول اتحاد فترات \(z\) الحالي، وهو بالضبط المقدار الذي يحتاجه خط المسح.
لنأخذ الصندوقين
$$C_1=[0,2)\times[0,3)\times[0,1),\qquad C_2=[1,3)\times[1,4)\times[0,2).$$
وهما يشغلان الشرائح \(x=0,1,2\).
عند \(x=0\) يكون \(C_1\) فقط فعالًا، ولذلك \(A_0=3\cdot 1=3\).
وعند \(x=1\) يكون الصندوقان فعالين معًا، والمستطيلان في المستوى \((y,z)\) هما
$$[0,3)\times[0,1),\qquad [1,4)\times[0,2).$$
ارتفاعات الأحداث هي \(0,1,3,4\). طول التغطية على محور \(z\) يساوي \(1\) على \([0,1)\)، ثم \(2\) على \([1,3)\)، ويبقى \(2\) على \([3,4)\). إذن
$$A_1=1\cdot(1-0)+2\cdot(3-1)+2\cdot(4-3)=7.$$
وعند \(x=2\) يبقى \(C_2\) فقط، لذا \(A_2=3\cdot 2=6\). ومن ثم
$$V=A_0+A_1+A_2=3+7+6=16.$$
هذا المثال الصغير يطابق البنية الهندسية للحل الكامل تمامًا: تحويل الحجم إلى مساحات شرائح، ثم تحويل مساحة كل شريحة إلى مسألة مسح للأحداث.
تبدأ تطبيقات C++ وPython وJava بتوليد أول \(6N\) قيمة من المتتالية، ثم تحويلها إلى \(50000\) متوازي مستطيلات نصف مفتوح. بعد ذلك تجري نسختا C++ وJava مرورًا بمصفوفة فروق على محور \(x\) لمعرفة عدد المستطيلات الفعالة في كل شريحة مقدمًا، وبالتالي يمكنهما حجز سعة مناسبة لكل شريحة. أما نسخة Python فتضيف مباشرة إلى القوائم، لكنها تبني الكيان الرياضي نفسه: لكل قيمة صحيحة لـ \(x\)، القائمة الكاملة لمستطيلات \((y,z)\) الموجودة داخل \([x,x+1)\).
تعالج كل شريحة على حدة. فإذا كانت الشريحة تحتوي على \(R_x\) مستطيلًا فعالًا، تُنشئ الشيفرة \(2R_x\) حدثًا، وترتبها حسب \(y\)، ثم تنفذ خط المسح مع تحديث شجرة مقاطع على المجال الأصلي لإحداثيات \(z\). لا حاجة هنا إلى ضغط الإحداثيات لأن القيم المولدة لا تتجاوز مجالًا حجمه يقارب \(10^4\). وبعد كل فجوة بين حدثين متتاليين، يُضرب طول التغطية الحالي الموجود في الجذر في ارتفاع تلك الفجوة ويُضاف إلى مساحة الشريحة.
بعد حساب جميع مساحات الشرائح، تُجمع مباشرة لإنتاج الحجم النهائي. تنفذ نسخة C++ توزيعًا ديناميكيًا للشرائح على عدة خيوط وتعيد استخدام بنية المسح لكل عامل. وتقسم نسخة Python مجال \(x\) إلى كتل وتحسب هذه الكتل في عمليات منفصلة. أما نسخة Java فتجري المسح نفسه شريحة بعد شريحة بصورة تسلسلية. كما تحتوي نسخة C++ أيضًا على اختبارات تحقق داخلية ضد أمثلة brute force صغيرة وضد قيمة تحقق معروفة لأول \(100\) صندوق.
ليكن \(R_x\) عدد المستطيلات الفعالة في الشريحة \(x\)، ولنعرّف
$$M=\sum_x R_x=\sum_{i=1}^{N} d_{x,i}.$$
وبما أن كل \(d_{x,i}\le 399\)، فلدينا حد صريح هو \(M\le 399N\). بناء جميع الصناديق يكلف \(O(N)\)، وتمثيلها عبر جميع الشرائح يكلف \(O(M)\) زمنًا و\(O(M)\) ذاكرة.
في كل شريحة تُرتب \(2R_x\) أحداث وتُجرى \(2R_x\) تحديثات على شجرة المقاطع، ولذلك يكون الزمن الكلي
$$O\!\left(\sum_x R_x\log R_x + M\log Z_{\max}\right),$$
حيث \(Z_{\max}\le 10398\). أما الذاكرة الإضافية لبنية مسح واحدة فهي \(O(Z_{\max})\)، ولذلك يمكن كتابة الذاكرة الكلية على صورة \(O(M+WZ_{\max})\) عند استخدام \(W\) عمال. عمليًا تنجح هذه الطريقة لأن حدود الإحداثيات في المسألة صغيرة بما يكفي للسماح بتخزين الشرائح صراحة.