As in Connections I, an array of \(2n\) elements in which every value occurs exactly twice defines \(n\) chords, one per value, joining its two positions. Now each chord may be drawn either above or below the row, and the array is bipartite-connectable when the chords can be split between the two sides so that no two chords on the same side cross.
Two chords that cross must go on opposite sides; two that do not cross may share a side. The input is guaranteed to be bipartite-connectable, and the task is to find the maximum number of chords that can be placed above the row in a valid drawing. The target instance has \(160\,000\) elements, i.e. \(n=80\,000\) chords.
For example \([0,1,2,1,0,2]\) is bipartite-connectable, and the maximum number of above-connections for it is \(2\).
Chords and the crossing relation are exactly as in Connections I: a value at positions \(p \lt q\) gives the interval \([p,q]\), and \([a,b]\), \([c,d]\) with \(a \lt c\) cross when they interleave, \(a \lt c \lt b \lt d\). Form the crossing graph \(G\): its vertices are the chords and its edges join crossing pairs.
Assigning every chord to "above" or "below" so that crossing chords land on opposite sides is exactly a proper \(2\)-colouring of \(G\) (above \(=\) colour \(0\), below \(=\) colour \(1\)). Such a colouring exists if and only if \(G\) is bipartite, i.e. contains no odd cycle. Three mutually crossing chords, for instance \([0,3],[1,4],[2,5]\) from \([0,1,2,0,1,2]\), form a triangle and make the array not bipartite-connectable.
When \(G\) is bipartite, each connected component admits exactly one \(2\)-colouring up to swapping its two colour classes. Since the components are independent, the number of chords sent above can be maximised component by component: for a component with colour classes of sizes \(c_0\) and \(c_1\), placing the larger class above contributes \(\max(c_0,c_1)\). Summing over components,
$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$
This is why the answer is a sum of per-component maxima rather than a global optimisation: cross-side constraints only couple chords inside the same connected component of \(G\).
Inside one connected component, a valid \(2\)-colouring has only two orientations: the first colour class above and the second below, or the reverse. There is no edge between different connected components, so choosing the orientation of one component cannot invalidate the orientation of another. Therefore each component contributes independently, and taking the larger colour class above in every component is both locally and globally optimal.
Bipartiteness and the colour-class sizes are computed together with a weighted (parity) disjoint-set structure. Every chord carries a parity equal to its colour relative to its component root; find returns the root together with that accumulated parity. Uniting two crossing chords imposes that their colours differ: if they already lie in the same component, the stored parities must disagree — if instead they agree, an odd cycle has been found and the array is not bipartite-connectable. Each root keeps a pair of counters \((c_0,c_1)\), the sizes of its two colour classes; merging two components combines these counters according to the linking parity, and the final answer sums \(\max(c_0,c_1)\) over the roots.
Suppose a crossing edge asks chords \(a\) and \(b\) to have opposite colours. If their roots are different, the union operation chooses a link parity \(t=p_a\oplus p_b\oplus 1\), where \(p_a\) and \(p_b\) are the parities returned by find. When one root is attached under the other, vertices whose old parity is \(t\) join colour class \(0\) of the new root, and vertices whose old parity is \(t\oplus1\) join colour class \(1\). This is the reason the size counters can be maintained without ever assigning absolute colours to all chords.
To find the edges of \(G\) without testing all \(\binom{n}{2}\) pairs, the chords are swept in order of left endpoint while an ordered set holds the currently open chords keyed by right endpoint. When chord \([\ell,r]\) opens, the chords that cross it are exactly the open ones whose right endpoint lies in the interval \((\ell,r)\): they began before \(\ell\) and end strictly between \(\ell\) and \(r\). An ordered-set range query returns them, and each is united with the current chord in the parity structure before \([\ell,r]\) itself is inserted. The sweep therefore enumerates precisely the crossing pairs.
The strict interval \((\ell,r)\) is important. A previous chord with right endpoint \(\le \ell\) is already disjoint from the current chord, so the range query skips it. A previous chord with right endpoint \(\ge r\) contains the current chord, so it is nested rather than crossing. Since every array position is a distinct endpoint, the only crossing case left is exactly \(\ell \lt \text{right} \lt r\), which is the range enumerated by the ordered set.
Value \(0\) is at positions \(0,4\); value \(1\) at \(1,3\); value \(2\) at \(2,5\). The chords are \([0,4]\), \([1,3]\), \([2,5]\). Here \([1,3]\) is nested inside \([0,4]\) (no crossing), while \([2,5]\) crosses both \([0,4]\) and \([1,3]\). The crossing graph is a single path on three vertices, with colour classes \(\{[2,5]\}\) and \(\{[0,4],[1,3]\}\). Placing the larger class above gives \(\max(1,2)=2\) above-connections, the stated answer.
The C++, Python, and Java implementations share the same pipeline. build_intervals records the first and second occurrence of each value, forms the chords, and sorts them by left endpoint. crosses tests the interleaving condition.
The ParityDsu structure implements the weighted union-find: find performs path compression while folding the parity to the root, unite merges by size and reports a conflict (odd cycle) when a crossing edge would join two equally coloured chords, best_sum returns \(\sum\max(c_0,c_1)\), and component_count counts the roots. solve_array runs the ordered-set sweep, uniting every crossing pair and bailing out the moment the graph proves non-bipartite.
The validation path is exhaustive on small inputs: brute_force_array lists the crossing edges and tries all \(2^n\) above/below assignments, keeping the largest valid above-count, and validate_all_words generates every array of length \(2n\) for \(n\le 4\) and checks that the fast solver agrees with the brute force on bipartiteness, the optimum, and the crossing count. run_checkpoints additionally pins the small cases \([0,1,2,1,0,2]\mapsto 2\), \([0,0,1,1,2,2]\mapsto 3\), and the non-bipartite \([0,1,2,0,1,2]\); main then solves the full instance.
Let \(C\) be the number of crossing pairs actually present. Building and sorting the chords costs \(O(n\log n)\); the sweep performs \(O(n+C)\) ordered-set operations at \(O(\log n)\) each and \(O(n+C)\) near-constant union-find operations, for an overall
$$O\bigl((n+C)\log n\bigr)$$
time and \(O(n)\) memory. On a bipartite-connectable input the sweep visits exactly the crossing edges rather than all \(\binom{n}{2}\) pairs. The brute-force checker is exponential, \(O(2^n)\), and runs only on the tiny validation arrays.
Wie bei Connections I definiert ein Array aus \(2n\) Elementen, in dem jeder Wert genau zweimal vorkommt, \(n\) Sehnen, eine pro Wert, die ihre beiden Positionen verbindet. Nun darf jede Sehne entweder oberhalb oder unterhalb der Reihe gezeichnet werden, und das Array ist bipartit-verbindbar, wenn die Sehnen so auf die beiden Seiten verteilt werden können, dass sich keine zwei Sehnen auf derselben Seite kreuzen.
Zwei Sehnen, die sich kreuzen, müssen auf entgegengesetzte Seiten; zwei, die sich nicht kreuzen, dürfen sich eine Seite teilen. Die Eingabe ist garantiert bipartit-verbindbar, und die Aufgabe besteht darin, die maximale Anzahl an Sehnen zu finden, die oberhalb der Reihe in einer gültigen Zeichnung platziert werden können. Die Zielinstanz hat \(160\,000\) Elemente, d. h. \(n=80\,000\) Sehnen.
Zum Beispiel ist \([0,1,2,1,0,2]\) bipartit-verbindbar, und die maximale Anzahl an Oberhalb-Verbindungen dafür ist \(2\).
Sehnen und die Kreuzungsrelation sind genau wie bei Connections I: ein Wert an den Positionen \(p \lt q\) ergibt das Intervall \([p,q]\), und \([a,b]\), \([c,d]\) mit \(a \lt c\) kreuzen sich, wenn sie verschachtelt sind, \(a \lt c \lt b \lt d\). Bilde den Kreuzungsgraphen \(G\): seine Knoten sind die Sehnen, und seine Kanten verbinden sich kreuzende Paare.
Jede Sehne "oberhalb" oder "unterhalb" so zuzuweisen, dass sich kreuzende Sehnen auf entgegengesetzten Seiten landen, ist genau eine zulässige \(2\)-Färbung von \(G\) (oberhalb \(=\) Farbe \(0\), unterhalb \(=\) Farbe \(1\)). Eine solche Färbung existiert genau dann, wenn \(G\) bipartit ist, d. h. keinen ungeraden Zyklus enthält. Drei sich paarweise kreuzende Sehnen, etwa \([0,3],[1,4],[2,5]\) aus \([0,1,2,0,1,2]\), bilden ein Dreieck und machen das Array nicht bipartit-verbindbar.
Wenn \(G\) bipartit ist, lässt jede Zusammenhangskomponente genau eine \(2\)-Färbung zu, bis auf das Vertauschen ihrer beiden Farbklassen. Da die Komponenten unabhängig sind, kann die Anzahl der nach oben gesendeten Sehnen Komponente für Komponente maximiert werden: für eine Komponente mit Farbklassen der Größen \(c_0\) und \(c_1\) liefert das Platzieren der größeren Klasse oberhalb \(\max(c_0,c_1)\). Summiert man über die Komponenten,
$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$
Deshalb ist die Antwort eine Summe von Komponenten-Maxima statt einer globalen Optimierung: Seitenübergreifende Einschränkungen koppeln nur Sehnen innerhalb derselben Zusammenhangskomponente von \(G\).
Innerhalb einer Zusammenhangskomponente hat eine gültige \(2\)-Färbung nur zwei Orientierungen: die erste Farbklasse oben und die zweite unten, oder umgekehrt. Zwischen verschiedenen Zusammenhangskomponenten gibt es keine Kante, daher kann die Orientierung einer Komponente die Orientierung einer anderen nicht ungültig machen. Jede Komponente trägt also unabhängig bei, und in jeder Komponente die größere Farbklasse nach oben zu legen ist lokal und global optimal.
Bipartitheit und die Größen der Farbklassen werden gemeinsam mit einer gewichteten (Paritäts-)Disjunkt-Mengen-Struktur berechnet. Jede Sehne trägt eine Parität gleich ihrer Farbe relativ zur Wurzel ihrer Komponente; find gibt die Wurzel zusammen mit dieser akkumulierten Parität zurück. Das Vereinigen zweier sich kreuzender Sehnen erzwingt, dass sich ihre Farben unterscheiden: liegen sie bereits in derselben Komponente, müssen die gespeicherten Paritäten nicht übereinstimmen — stimmen sie hingegen überein, wurde ein ungerader Zyklus gefunden und das Array ist nicht bipartit-verbindbar. Jede Wurzel führt ein Paar von Zählern \((c_0,c_1)\), die Größen ihrer beiden Farbklassen; das Verschmelzen zweier Komponenten kombiniert diese Zähler entsprechend der Verknüpfungsparität, und die endgültige Antwort summiert \(\max(c_0,c_1)\) über die Wurzeln.
Angenommen, eine Kreuzungskante verlangt, dass die Sehnen \(a\) und \(b\) verschiedene Farben haben. Sind ihre Wurzeln verschieden, wählt die Vereinigungsoperation eine Verknüpfungsparität \(t=p_a\oplus p_b\oplus 1\), wobei \(p_a\) und \(p_b\) die von find zurückgegebenen Paritäten sind. Wird eine Wurzel unter die andere gehängt, dann wandern die Knoten mit alter Parität \(t\) in Farbklasse \(0\) der neuen Wurzel, und die Knoten mit alter Parität \(t\oplus1\) in Farbklasse \(1\). Deshalb lassen sich die Größen der Farbklassen pflegen, ohne je allen Sehnen absolute Farben zuzuweisen.
Um die Kanten von \(G\) zu finden, ohne alle \(\binom{n}{2}\) Paare zu testen, werden die Sehnen in der Reihenfolge des linken Endpunkts überstrichen, während eine geordnete Menge die aktuell offenen Sehnen, geschlüsselt nach rechtem Endpunkt, enthält. Wenn die Sehne \([\ell,r]\) öffnet, sind die Sehnen, die sie kreuzen, genau die offenen, deren rechter Endpunkt im Intervall \((\ell,r)\) liegt: sie begannen vor \(\ell\) und enden strikt zwischen \(\ell\) und \(r\). Eine Bereichsabfrage auf der geordneten Menge gibt sie zurück, und jede wird mit der aktuellen Sehne in der Paritätsstruktur vereinigt, bevor \([\ell,r]\) selbst eingefügt wird. Der Sweep zählt daher genau die sich kreuzenden Paare auf.
Das strikte Intervall \((\ell,r)\) ist entscheidend. Eine frühere Sehne mit rechtem Endpunkt \(\le \ell\) ist bereits disjunkt zur aktuellen Sehne, also überspringt die Bereichsabfrage sie. Eine frühere Sehne mit rechtem Endpunkt \(\ge r\) enthält die aktuelle Sehne und ist daher verschachtelt statt kreuzend. Da jede Array-Position ein eigener Endpunkt ist, bleibt als Kreuzungsfall genau \(\ell \lt \text{right} \lt r\), und genau diesen Bereich zählt die geordnete Menge auf.
Wert \(0\) befindet sich an den Positionen \(0,4\); Wert \(1\) an \(1,3\); Wert \(2\) an \(2,5\). Die Sehnen sind \([0,4]\), \([1,3]\), \([2,5]\). Hier ist \([1,3]\) in \([0,4]\) verschachtelt (keine Kreuzung), während \([2,5]\) sowohl \([0,4]\) als auch \([1,3]\) kreuzt. Der Kreuzungsgraph ist ein einzelner Pfad auf drei Knoten, mit den Farbklassen \(\{[2,5]\}\) und \(\{[0,4],[1,3]\}\). Das Platzieren der größeren Klasse oberhalb ergibt \(\max(1,2)=2\) Oberhalb-Verbindungen, die angegebene Antwort.
Die C++-, Python- und Java-Implementierungen teilen sich dieselbe Pipeline. build_intervals erfasst das erste und zweite Vorkommen jedes Wertes, bildet die Sehnen und sortiert sie nach linkem Endpunkt. crosses testet die Verschachtelungsbedingung.
Die ParityDsu-Struktur implementiert das gewichtete Union-Find: find führt eine Pfadkompression durch, während es die Parität zur Wurzel hin faltet, unite verschmilzt nach Größe und meldet einen Konflikt (ungerader Zyklus), wenn eine Kreuzungskante zwei gleich gefärbte Sehnen verbinden würde, best_sum gibt \(\sum\max(c_0,c_1)\) zurück, und component_count zählt die Wurzeln. solve_array führt den Sweep über die geordnete Menge aus, vereinigt jedes sich kreuzende Paar und bricht in dem Moment ab, in dem sich der Graph als nicht bipartit erweist.
Der Validierungspfad ist für kleine Eingaben erschöpfend: brute_force_array listet die Kreuzungskanten auf und probiert alle \(2^n\) Oberhalb/Unterhalb-Zuweisungen aus, wobei es die größte gültige Oberhalb-Anzahl behält, und validate_all_words erzeugt jedes Array der Länge \(2n\) für \(n\le 4\) und prüft, dass der schnelle Löser mit der Brute-Force-Methode bei der Bipartitheit, dem Optimum und der Kreuzungsanzahl übereinstimmt. run_checkpoints fixiert zusätzlich die kleinen Fälle \([0,1,2,1,0,2]\mapsto 2\), \([0,0,1,1,2,2]\mapsto 3\) und das nicht-bipartite \([0,1,2,0,1,2]\); main löst dann die vollständige Instanz.
Sei \(C\) die Anzahl der tatsächlich vorhandenen sich kreuzenden Paare. Das Bilden und Sortieren der Sehnen kostet \(O(n\log n)\); der Sweep führt \(O(n+C)\) Operationen auf der geordneten Menge zu je \(O(\log n)\) und \(O(n+C)\) nahezu konstante Union-Find-Operationen durch, für insgesamt
$$O\bigl((n+C)\log n\bigr)$$
Zeit und \(O(n)\) Speicher. Bei einer bipartit-verbindbaren Eingabe besucht der Sweep genau die Kreuzungskanten statt aller \(\binom{n}{2}\) Paare. Der Brute-Force-Prüfer ist exponentiell, \(O(2^n)\), und läuft nur auf den winzigen Validierungsarrays.
Connections I'de olduğu gibi, her değerin tam olarak iki kez geçtiği \(2n\) elemanlı bir dizi, her değer için bir tane olmak üzere, o değerin iki konumunu birleştiren \(n\) kiriş tanımlar. Şimdi her kiriş satırın üstüne ya da altına çizilebilir ve dizi, kirişler iki taraf arasında, aynı tarafta hiçbir iki kiriş kesişmeyecek şekilde bölüştürülebildiğinde iki parçalı bağlanabilir olur.
Kesişen iki kiriş zıt taraflara gitmelidir; kesişmeyen iki kiriş aynı tarafı paylaşabilir. Girdinin iki parçalı bağlanabilir olduğu garanti edilir ve görev, geçerli bir çizimde satırın üstüne yerleştirilebilecek en fazla kiriş sayısını bulmaktır. Hedef örnek \(160\,000\) eleman içerir, yani \(n=80\,000\) kiriş.
Örneğin \([0,1,2,1,0,2]\) iki parçalı bağlanabilirdir ve bunun için üst bağlantıların maksimum sayısı \(2\)'dir.
Kirişler ve kesişme bağıntısı tam olarak Connections I'deki gibidir: \(p \lt q\) konumlarındaki bir değer \([p,q]\) aralığını verir ve \(a \lt c\) olmak üzere \([a,b]\), \([c,d]\), iç içe geçtiklerinde, yani \(a \lt c \lt b \lt d\) olduğunda kesişir. Kesişme grafiğini \(G\) oluşturun: köşeleri kirişlerdir ve kenarları kesişen çiftleri birleştirir.
Her kirişi, kesişen kirişler zıt taraflara düşecek şekilde "üst" ya da "alt" olarak atamak, tam olarak \(G\)'nin uygun bir \(2\)-renklendirmesidir (üst \(=\) renk \(0\), alt \(=\) renk \(1\)). Böyle bir renklendirme, ancak ve ancak \(G\) iki parçalı ise, yani tek uzunluklu döngü içermiyorsa vardır. Birbirini karşılıklı kesen üç kiriş, örneğin \([0,1,2,0,1,2]\) dizisinden \([0,3],[1,4],[2,5]\), bir üçgen oluşturur ve diziyi iki parçalı bağlanabilir olmaktan çıkarır.
\(G\) iki parçalı olduğunda, her bağlantılı bileşen, iki renk sınıfının yer değiştirmesi dışında tam olarak bir \(2\)-renklendirme kabul eder. Bileşenler bağımsız olduğundan, üste gönderilen kiriş sayısı bileşen bileşen maksimize edilebilir: renk sınıflarının boyutları \(c_0\) ve \(c_1\) olan bir bileşen için daha büyük sınıfı üste yerleştirmek \(\max(c_0,c_1)\) katkı yapar. Bileşenler üzerinden toplandığında,
$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$
Cevabın küresel bir optimizasyon yerine bileşen başına maksimumların bir toplamı olmasının nedeni budur: taraflar arası kısıtlar yalnızca \(G\)'nin aynı bağlantılı bileşeni içindeki kirişleri birbirine bağlar.
Tek bir bağlantılı bileşen içinde geçerli bir \(2\)-renklendirmenin yalnızca iki yönü vardır: birinci renk sınıfı üstte ve ikinci altta, ya da bunun tersi. Farklı bağlantılı bileşenler arasında kenar yoktur; bu yüzden bir bileşenin yönünü seçmek başka bir bileşenin yönünü geçersiz kılamaz. Böylece her bileşen bağımsız katkı yapar ve her bileşende daha büyük renk sınıfını üste almak hem yerel hem küresel olarak optimaldir.
İki parçalılık ve renk sınıfı boyutları, ağırlıklı (parite) ayrık-küme yapısıyla birlikte hesaplanır. Her kiriş, kendi bileşen kökü ile göreceli rengine eşit bir parite taşır; find kökü, biriken o parite ile birlikte döndürür. Kesişen iki kirişi birleştirmek, renklerinin farklı olmasını dayatır: eğer zaten aynı bileşendeyseler, saklanan paritelerin uyuşmaması gerekir — eğer aksine uyuşuyorlarsa, tek uzunluklu bir döngü bulunmuştur ve dizi iki parçalı bağlanabilir değildir. Her kök, iki renk sınıfının boyutları olan bir çift sayaç \((c_0,c_1)\) tutar; iki bileşeni birleştirmek bu sayaçları bağlama paritesine göre birleştirir ve nihai cevap kökler üzerinden \(\max(c_0,c_1)\) toplamını alır.
Bir kesişme kenarının \(a\) ve \(b\) kirişlerinin renklerinin farklı olmasını istediğini varsayın. Kökleri farklıysa birleştirme işlemi \(t=p_a\oplus p_b\oplus 1\) bağlantı paritesini seçer; burada \(p_a\) ve \(p_b\), find tarafından döndürülen paritelerdir. Bir kök diğerinin altına bağlandığında, eski paritesi \(t\) olan düğümler yeni kökün renk sınıfı \(0\)'ına, eski paritesi \(t\oplus1\) olan düğümler renk sınıfı \(1\)'ine katılır. Bu nedenle renk sınıfı boyutları, tüm kirişlere mutlak renkler atanmadan korunabilir.
\(G\)'nin kenarlarını tüm \(\binom{n}{2}\) çifti test etmeden bulmak için, kirişler sol uç noktaya göre sırayla taranırken, sıralı bir küme o anda açık olan kirişleri sağ uç noktaya göre anahtarlanmış olarak tutar. \([\ell,r]\) kirişi açıldığında, onu kesen kirişler tam olarak sağ uç noktası \((\ell,r)\) aralığında bulunan açık kirişlerdir: bunlar \(\ell\)'den önce başlamış ve kesin olarak \(\ell\) ile \(r\) arasında bitmiştir. Bir sıralı-küme aralık sorgusu bunları döndürür ve \([\ell,r]\)'nin kendisi eklenmeden önce her biri geçerli kirişle parite yapısında birleştirilir. Böylece tarama tam olarak kesişen çiftleri sıralar.
Sıkı \((\ell,r)\) aralığı önemlidir. Sağ uç noktası \(\le \ell\) olan önceki bir kiriş geçerli kirişten zaten ayrıdır, bu nedenle aralık sorgusu onu atlar. Sağ uç noktası \(\ge r\) olan önceki bir kiriş ise geçerli kirişi içerir; bu kesişme değil yuvalanmadır. Her dizi konumu farklı bir uç nokta olduğundan geriye kalan tek kesişme durumu tam olarak \(\ell \lt \text{right} \lt r\) olur; sıralı kümenin numaralandırdığı aralık da budur.
Değer \(0\), \(0,4\) konumlarında; değer \(1\), \(1,3\)'te; değer \(2\), \(2,5\)'te. Kirişler \([0,4]\), \([1,3]\), \([2,5]\). Burada \([1,3]\), \([0,4]\)'ün içine yuvalanmıştır (kesişme yok), oysa \([2,5]\) hem \([0,4]\)'ü hem de \([1,3]\)'ü keser. Kesişme grafiği üç köşe üzerinde tek bir yoldur ve renk sınıfları \(\{[2,5]\}\) ile \(\{[0,4],[1,3]\}\)'tür. Daha büyük sınıfı üste yerleştirmek \(\max(1,2)=2\) üst bağlantı verir; belirtilen cevap budur.
C++, Python ve Java uygulamaları aynı işlem hattını paylaşır. build_intervals her değerin ilk ve ikinci geçişini kaydeder, kirişleri oluşturur ve onları sol uç noktaya göre sıralar. crosses iç içe geçme koşulunu test eder.
ParityDsu yapısı ağırlıklı birleştir-bul yapısını uygular: find pariteyi köke katlarken yol sıkıştırması yapar, unite boyuta göre birleştirir ve kesişen bir kenar eşit renklendirilmiş iki kirişi birleştirecek olduğunda bir çakışma (tek uzunluklu döngü) bildirir, best_sum \(\sum\max(c_0,c_1)\) döndürür ve component_count kökleri sayar. solve_array sıralı-küme taramasını çalıştırır, her kesişen çifti birleştirir ve grafiğin iki parçalı olmadığı kanıtlandığı anda işlemi durdurur.
Doğrulama yolu küçük girdilerde tüketicidir: brute_force_array kesişen kenarları listeler ve tüm \(2^n\) üst/alt atamasını deneyerek geçerli en büyük üst sayımını saklar, validate_all_words ise \(n\le 4\) için \(2n\) uzunluğundaki her diziyi üretir ve hızlı çözücünün iki parçalılık, optimum ve kesişme sayısı konusunda kaba kuvvetle uyuştuğunu kontrol eder. run_checkpoints ek olarak küçük durumları sabitler: \([0,1,2,1,0,2]\mapsto 2\), \([0,0,1,1,2,2]\mapsto 3\) ve iki parçalı olmayan \([0,1,2,0,1,2]\); ardından main tam örneği çözer.
\(C\), gerçekte var olan kesişen çiftlerin sayısı olsun. Kirişleri oluşturmak ve sıralamak \(O(n\log n)\) maliyetindedir; tarama, her biri \(O(\log n)\) olan \(O(n+C)\) sıralı-küme işlemi ve \(O(n+C)\) neredeyse sabit birleştir-bul işlemi gerçekleştirir, böylece toplamda
$$O\bigl((n+C)\log n\bigr)$$
zaman ve \(O(n)\) bellek. İki parçalı bağlanabilir bir girdide tarama, tüm \(\binom{n}{2}\) çift yerine tam olarak kesişen kenarları ziyaret eder. Kaba kuvvet denetleyicisi üsteldir, \(O(2^n)\), ve yalnızca minik doğrulama dizilerinde çalışır.
Como en Conexiones I, un arreglo de \(2n\) elementos en el que cada valor aparece exactamente dos veces define \(n\) cuerdas, una por valor, que unen sus dos posiciones. Ahora cada cuerda puede dibujarse ya sea por encima o por debajo de la fila, y el arreglo es conectable de forma bipartita cuando las cuerdas pueden repartirse entre los dos lados de modo que ningún par de cuerdas del mismo lado se cruce.
Dos cuerdas que se cruzan deben ir en lados opuestos; dos que no se cruzan pueden compartir un lado. Se garantiza que la entrada es conectable de forma bipartita, y la tarea consiste en hallar el número máximo de cuerdas que pueden colocarse por encima de la fila en un dibujo válido. La instancia objetivo tiene \(160\,000\) elementos, es decir \(n=80\,000\) cuerdas.
Por ejemplo \([0,1,2,1,0,2]\) es conectable de forma bipartita, y el número máximo de conexiones por encima para él es \(2\).
Las cuerdas y la relación de cruce son exactamente como en Conexiones I: un valor en las posiciones \(p \lt q\) da el intervalo \([p,q]\), y \([a,b]\), \([c,d]\) con \(a \lt c\) se cruzan cuando se entrelazan, \(a \lt c \lt b \lt d\). Forme el grafo de cruces \(G\): sus vértices son las cuerdas y sus aristas unen los pares que se cruzan.
Asignar cada cuerda a "por encima" o "por debajo" de modo que las cuerdas que se cruzan caigan en lados opuestos es exactamente una \(2\)-coloración propia de \(G\) (por encima \(=\) color \(0\), por debajo \(=\) color \(1\)). Tal coloración existe si y solo si \(G\) es bipartito, es decir, no contiene ningún ciclo impar. Tres cuerdas que se cruzan mutuamente, por ejemplo \([0,3],[1,4],[2,5]\) de \([0,1,2,0,1,2]\), forman un triángulo y hacen que el arreglo no sea conectable de forma bipartita.
Cuando \(G\) es bipartito, cada componente conexa admite exactamente una \(2\)-coloración salvo el intercambio de sus dos clases de color. Como las componentes son independientes, el número de cuerdas enviadas por encima puede maximizarse componente por componente: para una componente con clases de color de tamaños \(c_0\) y \(c_1\), colocar la clase más grande por encima aporta \(\max(c_0,c_1)\). Sumando sobre las componentes,
$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$
Por esto la respuesta es una suma de máximos por componente en lugar de una optimización global: las restricciones de lados opuestos solo acoplan cuerdas dentro de la misma componente conexa de \(G\).
Dentro de una componente conexa, una \(2\)-coloración válida tiene solo dos orientaciones: la primera clase de color arriba y la segunda abajo, o al revés. No hay aristas entre componentes conexas distintas, así que elegir la orientación de una componente no puede invalidar la orientación de otra. Por tanto, cada componente contribuye de forma independiente, y colocar arriba la clase de color mayor en cada componente es óptimo tanto local como globalmente.
La bipartición y los tamaños de las clases de color se calculan conjuntamente con una estructura de conjuntos disjuntos ponderada (con paridad). Cada cuerda lleva una paridad igual a su color relativo a la raíz de su componente; find devuelve la raíz junto con esa paridad acumulada. Unir dos cuerdas que se cruzan impone que sus colores difieran: si ya están en la misma componente, las paridades almacenadas deben discrepar — si en cambio coinciden, se ha encontrado un ciclo impar y el arreglo no es conectable de forma bipartita. Cada raíz mantiene un par de contadores \((c_0,c_1)\), los tamaños de sus dos clases de color; al fusionar dos componentes se combinan estos contadores según la paridad del enlace, y la respuesta final suma \(\max(c_0,c_1)\) sobre las raíces.
Suponga que una arista de cruce exige que las cuerdas \(a\) y \(b\) tengan colores opuestos. Si sus raíces son distintas, la operación de unión escoge una paridad de enlace \(t=p_a\oplus p_b\oplus 1\), donde \(p_a\) y \(p_b\) son las paridades devueltas por find. Cuando una raíz se cuelga bajo la otra, los vértices cuya antigua paridad es \(t\) entran en la clase de color \(0\) de la nueva raíz, y los de antigua paridad \(t\oplus1\) entran en la clase de color \(1\). Por eso los contadores de tamaño pueden mantenerse sin asignar colores absolutos a todas las cuerdas.
Para hallar las aristas de \(G\) sin probar todos los \(\binom{n}{2}\) pares, las cuerdas se barren en orden de extremo izquierdo mientras un conjunto ordenado contiene las cuerdas actualmente abiertas indexadas por extremo derecho. Cuando la cuerda \([\ell,r]\) se abre, las cuerdas que la cruzan son exactamente las abiertas cuyo extremo derecho se encuentra en el intervalo \((\ell,r)\): comenzaron antes de \(\ell\) y terminan estrictamente entre \(\ell\) y \(r\). Una consulta de rango sobre el conjunto ordenado las devuelve, y cada una se une con la cuerda actual en la estructura de paridad antes de que \([\ell,r]\) se inserte. El barrido, por tanto, enumera precisamente los pares que se cruzan.
El intervalo estricto \((\ell,r)\) es importante. Una cuerda anterior con extremo derecho \(\le \ell\) ya es disjunta de la cuerda actual, por lo que la consulta de rango la omite. Una cuerda anterior con extremo derecho \(\ge r\) contiene a la cuerda actual, de modo que está anidada y no se cruza con ella. Como cada posición del arreglo es un extremo distinto, el único caso de cruce restante es exactamente \(\ell \lt \text{right} \lt r\), que es el rango enumerado por el conjunto ordenado.
El valor \(0\) está en las posiciones \(0,4\); el valor \(1\) en \(1,3\); el valor \(2\) en \(2,5\). Las cuerdas son \([0,4]\), \([1,3]\), \([2,5]\). Aquí \([1,3]\) está anidada dentro de \([0,4]\) (sin cruce), mientras que \([2,5]\) cruza tanto a \([0,4]\) como a \([1,3]\). El grafo de cruces es un único camino sobre tres vértices, con clases de color \(\{[2,5]\}\) y \(\{[0,4],[1,3]\}\). Colocar la clase más grande por encima da \(\max(1,2)=2\) conexiones por encima, la respuesta enunciada.
Las implementaciones en C++, Python y Java comparten la misma canalización. build_intervals registra la primera y la segunda aparición de cada valor, forma las cuerdas y las ordena por extremo izquierdo. crosses comprueba la condición de entrelazado.
La estructura ParityDsu implementa el union-find ponderado: find realiza compresión de caminos a la vez que pliega la paridad hasta la raíz, unite fusiona por tamaño e informa de un conflicto (ciclo impar) cuando una arista de cruce uniría dos cuerdas igualmente coloreadas, best_sum devuelve \(\sum\max(c_0,c_1)\), y component_count cuenta las raíces. solve_array ejecuta el barrido con conjunto ordenado, uniendo cada par que se cruza y abortando en el momento en que el grafo resulta no bipartito.
La vía de validación es exhaustiva en entradas pequeñas: brute_force_array lista las aristas de cruce y prueba todas las \(2^n\) asignaciones por encima/por debajo, conservando el mayor recuento por encima válido, y validate_all_words genera cada arreglo de longitud \(2n\) para \(n\le 4\) y comprueba que el solucionador rápido coincide con la fuerza bruta en la bipartición, el óptimo y el recuento de cruces. run_checkpoints además fija los casos pequeños \([0,1,2,1,0,2]\mapsto 2\), \([0,0,1,1,2,2]\mapsto 3\), y el no bipartito \([0,1,2,0,1,2]\); main resuelve entonces la instancia completa.
Sea \(C\) el número de pares que se cruzan realmente presentes. Construir y ordenar las cuerdas cuesta \(O(n\log n)\); el barrido realiza \(O(n+C)\) operaciones sobre el conjunto ordenado a \(O(\log n)\) cada una y \(O(n+C)\) operaciones de union-find casi constantes, para un total de
$$O\bigl((n+C)\log n\bigr)$$
tiempo y \(O(n)\) memoria. En una entrada conectable de forma bipartita el barrido visita exactamente las aristas de cruce en lugar de todos los \(\binom{n}{2}\) pares. El verificador de fuerza bruta es exponencial, \(O(2^n)\), y solo se ejecuta sobre los pequeños arreglos de validación.
与连接问题 I 一样，一个包含 \(2n\) 个元素的数组（其中每个值恰好出现两次）定义了 \(n\) 条弦，每个值对应一条，连接它的两个位置。现在每条弦既可以画在该行的上方，也可以画在下方，当这些弦能够分配到两侧、使得同一侧上没有两条弦相交时，该数组就是可二部连接的。
两条相交的弦必须位于相对的两侧；两条不相交的弦则可以共享同一侧。输入保证是可二部连接的，任务是找出在一个有效画法中能够放置在该行上方的最大弦数。目标实例有 \(160\,000\) 个元素，即 \(n=80\,000\) 条弦。
例如 \([0,1,2,1,0,2]\) 是可二部连接的，它的上方连接数最大值为 \(2\)。
弦与相交关系与连接问题 I 中完全相同：位于位置 \(p \lt q\) 的某个值给出区间 \([p,q]\)，而 \([a,b]\)、\([c,d]\)（其中 \(a \lt c\)）在它们交错时相交，即 \(a \lt c \lt b \lt d\)。构造相交图 \(G\)：它的顶点是这些弦，它的边连接相交的弦对。
将每条弦分配为"上方"或"下方"，使得相交的弦落在相对的两侧，这恰好是 \(G\) 的一个正常 \(2\)-着色（上方 \(=\) 颜色 \(0\)，下方 \(=\) 颜色 \(1\)）。这样的着色存在当且仅当 \(G\) 是二部图，即不含奇环。三条两两相交的弦，例如来自 \([0,1,2,0,1,2]\) 的 \([0,3],[1,4],[2,5]\)，构成一个三角形，使得该数组不可二部连接。
当 \(G\) 是二部图时，每个连通分量都恰好有一种 \(2\)-着色（在交换其两个颜色类之前是唯一的）。由于各分量相互独立，送往上方的弦数可以逐个分量地最大化：对于一个颜色类大小为 \(c_0\) 和 \(c_1\) 的分量，将较大的类放在上方贡献 \(\max(c_0,c_1)\)。对所有分量求和，
$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$
这就是为什么答案是各分量最大值之和，而不是一个全局优化问题：跨侧约束只在 \(G\) 的同一连通分量内部耦合弦。
在一个连通分量内部，一个合法的 \(2\)-着色只有两种方向：第一颜色类在上、第二颜色类在下，或者反过来。不同连通分量之间没有边，所以一个分量的方向选择不会使另一个分量的方向失效。因此各分量独立贡献，在每个分量中把较大的颜色类放在上方，既是局部最优也是全局最优。
二部性和颜色类大小是通过一个带权（奇偶性）不相交集合结构一起计算的。每条弦携带一个奇偶值，等于它相对于其分量根的颜色；find 返回根以及那个累积的奇偶值。合并两条相交的弦时强制它们的颜色不同：如果它们已经位于同一分量中，存储的奇偶值必须不一致——如果反而一致，则找到了一个奇环，该数组不可二部连接。每个根保存一对计数器 \((c_0,c_1)\)，即它两个颜色类的大小；合并两个分量时根据链接奇偶性组合这些计数器，最终答案对各根求 \(\max(c_0,c_1)\) 之和。
假设一条相交边要求弦 \(a\) 与弦 \(b\) 颜色相反。如果它们的根不同，合并操作会选择链接奇偶值 \(t=p_a\oplus p_b\oplus 1\)，其中 \(p_a\) 与 \(p_b\) 是 find 返回的奇偶值。当一个根挂到另一个根下面时，旧奇偶值为 \(t\) 的顶点进入新根的颜色类 \(0\)，旧奇偶值为 \(t\oplus1\) 的顶点进入颜色类 \(1\)。因此不必给所有弦显式分配绝对颜色，也能维护两个颜色类的大小。
为了在不测试全部 \(\binom{n}{2}\) 对的情况下找出 \(G\) 的边，按左端点的顺序扫描这些弦，同时用一个有序集合保存当前开放的弦，以右端点为键。当弦 \([\ell,r]\) 开放时，与它相交的弦恰好是那些右端点位于区间 \((\ell,r)\) 内的开放弦：它们在 \(\ell\) 之前开始，并在 \(\ell\) 与 \(r\) 之间严格结束。一次有序集合范围查询将它们返回，并在插入 \([\ell,r]\) 自身之前，将每一条与当前弦在奇偶性结构中合并。因此扫描线恰好枚举了相交对。
严格区间 \((\ell,r)\) 很关键。若先前一条弦的右端点 \(\le \ell\)，它已经与当前弦不相交，因此范围查询跳过它。若先前一条弦的右端点 \(\ge r\)，它包含当前弦，所以是嵌套而不是相交。由于数组中的每个位置都是不同的端点，剩下的唯一相交情形正是 \(\ell \lt \text{right} \lt r\)，这也正是有序集合枚举的范围。
值 \(0\) 位于位置 \(0,4\)；值 \(1\) 位于 \(1,3\)；值 \(2\) 位于 \(2,5\)。这些弦是 \([0,4]\)、\([1,3]\)、\([2,5]\)。这里 \([1,3]\) 嵌套在 \([0,4]\) 内部（不相交），而 \([2,5]\) 同时与 \([0,4]\) 和 \([1,3]\) 相交。相交图是一条三个顶点的单一路径，其颜色类为 \(\{[2,5]\}\) 和 \(\{[0,4],[1,3]\}\)。将较大的类放在上方得到 \(\max(1,2)=2\) 个上方连接，即所述答案。
C++、Python 和 Java 实现共享同一条流水线。build_intervals 记录每个值的第一次和第二次出现，构造这些弦，并按左端点对它们排序。crosses 测试交错条件。
ParityDsu 结构实现了带权并查集：find 在执行路径压缩的同时将奇偶性折叠到根上，unite 按大小合并，并在一条相交边会连接两条同色弦时报告冲突（奇环），best_sum 返回 \(\sum\max(c_0,c_1)\)，而 component_count 统计根的数量。solve_array 运行有序集合扫描线，合并每一对相交对，并在该图被证明为非二部图的那一刻立即退出。
验证路径在小输入上是穷举式的：brute_force_array 列出相交边并尝试所有 \(2^n\) 种上方/下方分配，保留最大的有效上方计数，而 validate_all_words 生成所有长度为 \(2n\)（\(n\le 4\)）的数组，并检查快速求解器在二部性、最优值和相交计数上与暴力法一致。run_checkpoints 还额外固定了小情形 \([0,1,2,1,0,2]\mapsto 2\)、\([0,0,1,1,2,2]\mapsto 3\) 以及非二部的 \([0,1,2,0,1,2]\)；main 随后求解完整实例。
设 \(C\) 为实际存在的相交对数。构造并排序这些弦的代价为 \(O(n\log n)\)；扫描线执行 \(O(n+C)\) 次有序集合操作（每次 \(O(\log n)\)）以及 \(O(n+C)\) 次近似常数时间的并查集操作，总体为
$$O\bigl((n+C)\log n\bigr)$$
的时间和 \(O(n)\) 的内存。在可二部连接的输入上，扫描线恰好访问那些相交边，而不是全部 \(\binom{n}{2}\) 对。暴力检查器是指数级的 \(O(2^n)\)，仅在极小的验证数组上运行。
Как и в Connections I, массив из \(2n\) элементов, в котором каждое значение встречается ровно дважды, задаёт \(n\) хорд, по одной на значение, соединяющих две его позиции. Теперь каждую хорду можно нарисовать либо над рядом, либо под ним, и массив называется двудольно-соединимым, когда хорды можно разделить между двумя сторонами так, чтобы никакие две хорды на одной стороне не пересекались.
Две пересекающиеся хорды должны попасть на противоположные стороны; две непересекающиеся могут разделять одну сторону. Гарантируется, что вход двудольно-соединим, и задача состоит в том, чтобы найти максимальное число хорд, которые можно разместить над рядом в допустимом рисунке. Целевой экземпляр содержит \(160\,000\) элементов, то есть \(n=80\,000\) хорд.
Например, \([0,1,2,1,0,2]\) двудольно-соединим, и максимальное число верхних соединений для него равно \(2\).
Хорды и отношение пересечения такие же, как в Connections I: значение в позициях \(p \lt q\) задаёт интервал \([p,q]\), а \([a,b]\), \([c,d]\) с \(a \lt c\) пересекаются, когда они чередуются, \(a \lt c \lt b \lt d\). Образуем граф пересечений \(G\): его вершины — это хорды, а рёбра соединяют пересекающиеся пары.
Назначение каждой хорды «над» или «под» так, чтобы пересекающиеся хорды попадали на противоположные стороны, — это в точности правильная \(2\)-раскраска графа \(G\) (над \(=\) цвет \(0\), под \(=\) цвет \(1\)). Такая раскраска существует тогда и только тогда, когда \(G\) двудольный, то есть не содержит нечётного цикла. Три взаимно пересекающиеся хорды, например \([0,3],[1,4],[2,5]\) из \([0,1,2,0,1,2]\), образуют треугольник и делают массив не двудольно-соединимым.
Когда \(G\) двудольный, каждая связная компонента допускает ровно одну \(2\)-раскраску с точностью до перестановки двух её цветовых классов. Поскольку компоненты независимы, число хорд, отправленных наверх, можно максимизировать покомпонентно: для компоненты с цветовыми классами размеров \(c_0\) и \(c_1\) размещение большего класса сверху даёт \(\max(c_0,c_1)\). Суммируя по компонентам,
$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$
Вот почему ответ — это сумма покомпонентных максимумов, а не глобальная оптимизация: ограничения на стороны связывают между собой только хорды внутри одной связной компоненты графа \(G\).
Внутри одной связной компоненты допустимая \(2\)-раскраска имеет только две ориентации: первый цветовой класс сверху и второй снизу, либо наоборот. Между разными связными компонентами нет рёбер, поэтому выбор ориентации одной компоненты не может нарушить ориентацию другой. Следовательно, каждая компонента даёт независимый вклад, а размещение большего цветового класса сверху в каждой компоненте является и локально, и глобально оптимальным.
Двудольность и размеры цветовых классов вычисляются совместно при помощи взвешенной (по чётности) структуры непересекающихся множеств. Каждая хорда несёт чётность, равную её цвету относительно корня её компоненты; find возвращает корень вместе с этой накопленной чётностью. Объединение двух пересекающихся хорд требует, чтобы их цвета различались: если они уже лежат в одной компоненте, сохранённые чётности должны не совпадать — если же они совпадают, обнаружен нечётный цикл, и массив не является двудольно-соединимым. Каждый корень хранит пару счётчиков \((c_0,c_1)\) — размеры его двух цветовых классов; слияние двух компонент комбинирует эти счётчики согласно чётности связи, а итоговый ответ суммирует \(\max(c_0,c_1)\) по корням.
Пусть ребро пересечения требует, чтобы хорды \(a\) и \(b\) имели разные цвета. Если их корни различны, операция объединения выбирает чётность связи \(t=p_a\oplus p_b\oplus 1\), где \(p_a\) и \(p_b\) являются чётностями, возвращёнными find. Когда один корень подвешивается под другой, вершины со старой чётностью \(t\) переходят в цветовой класс \(0\) нового корня, а вершины со старой чётностью \(t\oplus1\) переходят в цветовой класс \(1\). Поэтому размеры цветовых классов можно поддерживать, не назначая абсолютные цвета всем хордам.
Чтобы найти рёбра графа \(G\), не проверяя все \(\binom{n}{2}\) пар, хорды просматриваются в порядке левого конца, в то время как упорядоченное множество хранит текущие открытые хорды с ключом по правому концу. Когда хорда \([\ell,r]\) открывается, пересекающие её хорды — это в точности те открытые, чей правый конец лежит в интервале \((\ell,r)\): они начались до \(\ell\) и заканчиваются строго между \(\ell\) и \(r\). Диапазонный запрос к упорядоченному множеству возвращает их, и каждая объединяется с текущей хордой в структуре чётности, прежде чем сама \([\ell,r]\) будет вставлена. Таким образом, развёртка перечисляет в точности пересекающиеся пары.
Строгий интервал \((\ell,r)\) важен. Предыдущая хорда с правым концом \(\le \ell\) уже не пересекается с текущей, поэтому диапазонный запрос её пропускает. Предыдущая хорда с правым концом \(\ge r\) содержит текущую хорду, значит она вложена, а не пересекается. Поскольку каждая позиция массива является отдельным концом, единственный оставшийся случай пересечения это ровно \(\ell \lt \text{right} \lt r\), и именно этот диапазон перечисляет упорядоченное множество.
Значение \(0\) находится в позициях \(0,4\); значение \(1\) — в \(1,3\); значение \(2\) — в \(2,5\). Хорды — это \([0,4]\), \([1,3]\), \([2,5]\). Здесь \([1,3]\) вложена в \([0,4]\) (без пересечения), тогда как \([2,5]\) пересекает обе хорды \([0,4]\) и \([1,3]\). Граф пересечений — это единственный путь на трёх вершинах, с цветовыми классами \(\{[2,5]\}\) и \(\{[0,4],[1,3]\}\). Размещение большего класса сверху даёт \(\max(1,2)=2\) верхних соединения — заявленный ответ.
Реализации на C++, Python и Java используют один и тот же конвейер. build_intervals записывает первое и второе вхождение каждого значения, формирует хорды и сортирует их по левому концу. crosses проверяет условие чередования.
Структура ParityDsu реализует взвешенную систему непересекающихся множеств: find выполняет сжатие путей, сворачивая чётность к корню, unite объединяет по размеру и сообщает о конфликте (нечётный цикл), когда пересекающее ребро соединило бы две одинаково окрашенные хорды, best_sum возвращает \(\sum\max(c_0,c_1)\), а component_count подсчитывает корни. solve_array запускает развёртку по упорядоченному множеству, объединяя каждую пересекающуюся пару и прекращая работу в тот момент, когда граф оказывается недвудольным.
Путь проверки является исчерпывающим на малых входах: brute_force_array перечисляет рёбра пересечений и перебирает все \(2^n\) назначений над/под, сохраняя наибольшее допустимое число верхних, а validate_all_words генерирует каждый массив длины \(2n\) для \(n\le 4\) и проверяет, что быстрый решатель согласуется с полным перебором по двудольности, оптимуму и числу пересечений. run_checkpoints дополнительно фиксирует малые случаи \([0,1,2,1,0,2]\mapsto 2\), \([0,0,1,1,2,2]\mapsto 3\) и недвудольный \([0,1,2,0,1,2]\); затем main решает полный экземпляр.
Пусть \(C\) — фактически присутствующее число пересекающихся пар. Построение и сортировка хорд стоят \(O(n\log n)\); развёртка выполняет \(O(n+C)\) операций над упорядоченным множеством по \(O(\log n)\) каждая и \(O(n+C)\) почти константных операций системы непересекающихся множеств, что даёт в целом
$$O\bigl((n+C)\log n\bigr)$$
времени и \(O(n)\) памяти. На двудольно-соединимом входе развёртка посещает в точности рёбра пересечений, а не все \(\binom{n}{2}\) пар. Проверщик полным перебором экспоненциален, \(O(2^n)\), и запускается только на крошечных проверочных массивах.
كما في "الوصلات I"، فإن مصفوفة مكوّنة من \(2n\) عنصرًا تظهر فيها كل قيمة مرتين بالضبط تُعرّف \(n\) وترًا، وترًا واحدًا لكل قيمة، يصل بين موضعيها. والآن يمكن رسم كل وتر إما فوق الصف أو تحته، وتكون المصفوفة قابلة للوصل الثنائي عندما يمكن تقسيم الأوتار بين الجانبين بحيث لا يتقاطع وتران على الجانب نفسه.
الوتران اللذان يتقاطعان يجب أن يقعا على جانبين متقابلين؛ والوتران اللذان لا يتقاطعان يجوز أن يتشاركا الجانب نفسه. وتضمن المدخلات أنها قابلة للوصل الثنائي، والمهمة هي إيجاد أكبر عدد من الأوتار التي يمكن وضعها فوق الصف في رسم صحيح. تحتوي الحالة المطلوبة على \(160\,000\) عنصر، أي \(n=80\,000\) وتر.
على سبيل المثال \([0,1,2,1,0,2]\) قابلة للوصل الثنائي، والعدد الأقصى للوصلات الفوقية لها هو \(2\).
الأوتار وعلاقة التقاطع هي تمامًا كما في "الوصلات I": قيمة عند الموضعين \(p \lt q\) تعطي الفترة \([p,q]\)، والفترتان \([a,b]\) و\([c,d]\) حيث \(a \lt c\) تتقاطعان عندما تتشابكان، أي \(a \lt c \lt b \lt d\). نكوّن مخطط التقاطع \(G\): رؤوسه هي الأوتار وأضلاعه تصل بين الأزواج المتقاطعة.
إن تعيين كل وتر إلى "فوق" أو "تحت" بحيث تقع الأوتار المتقاطعة على جانبين متقابلين هو بالضبط تلوين سليم بـ\(2\) لون للمخطط \(G\) (فوق \(=\) اللون \(0\)، تحت \(=\) اللون \(1\)). يوجد مثل هذا التلوين إذا وفقط إذا كان \(G\) ثنائيًا، أي لا يحتوي على دورة فردية. ثلاثة أوتار يتقاطع كل منها مع الآخر، مثل \([0,3],[1,4],[2,5]\) من \([0,1,2,0,1,2]\)، تكوّن مثلثًا وتجعل المصفوفة غير قابلة للوصل الثنائي.
عندما يكون \(G\) ثنائيًا، يقبل كل مكوّن متصل تلوينًا واحدًا بالضبط بـ\(2\) لون بصرف النظر عن تبديل صنفَي لونيه. وبما أن المكوّنات مستقلة، يمكن تعظيم عدد الأوتار المرسلة إلى الأعلى مكوّنًا بمكوّن: بالنسبة لمكوّن صنفا لونه بحجمَي \(c_0\) و\(c_1\)، فإن وضع الصنف الأكبر في الأعلى يسهم بـ \(\max(c_0,c_1)\). وبالجمع على المكوّنات،
$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$
وهذا هو سبب كون الجواب مجموعًا لقيم عظمى لكل مكوّن على حدة بدلًا من تحسين شامل: القيود بين الجانبين لا تربط إلا الأوتار داخل المكوّن المتصل نفسه من \(G\).
داخل مكوّن متصل واحد لا يملك أي تلوين صحيح بلونين إلا اتجاهين: صنف اللون الأول في الأعلى والثاني في الأسفل، أو العكس. ولا توجد أضلاع بين مكوّنات متصلة مختلفة، لذلك لا يمكن لاختيار اتجاه مكوّن أن يفسد اتجاه مكوّن آخر. ومن ثم يسهم كل مكوّن باستقلال، ووضع صنف اللون الأكبر في الأعلى داخل كل مكوّن هو اختيار أمثل محليًا وعالميًا.
تُحسب الثنائية وأحجام أصناف الألوان معًا باستخدام بنية مجموعات منفصلة موزونة (بالتكافؤ). يحمل كل وتر تكافؤًا يساوي لونه بالنسبة إلى جذر مكوّنه؛ وتعيد find الجذر مع ذلك التكافؤ المتراكم. إن اتحاد وترين متقاطعين يفرض أن يختلف لوناهما: إن كانا أصلًا في المكوّن نفسه، يجب أن يتعارض التكافؤان المخزّنان — وإن اتفقا بدلًا من ذلك، فقد عُثر على دورة فردية والمصفوفة غير قابلة للوصل الثنائي. يحتفظ كل جذر بزوج من العدادات \((c_0,c_1)\)، أحجام صنفَي لونيه؛ ودمج مكوّنين يجمع هذه العدادات وفق تكافؤ الربط، والجواب النهائي يجمع \(\max(c_0,c_1)\) على الجذور.
لنفترض أن ضلع تقاطع يطلب أن يكون لوتري \(a\) و\(b\) لونان مختلفان. إذا كان جذراهما مختلفين، تختار عملية الاتحاد تكافؤ ربط \(t=p_a\oplus p_b\oplus 1\)، حيث \(p_a\) و\(p_b\) هما التكافؤان اللذان تعيدهما find. وعندما يُعلّق جذر تحت الآخر، فإن الرؤوس ذات التكافؤ القديم \(t\) تنضم إلى صنف اللون \(0\) للجذر الجديد، والرؤوس ذات التكافؤ القديم \(t\oplus1\) تنضم إلى صنف اللون \(1\). لذلك يمكن حفظ أحجام أصناف الألوان من دون إعطاء ألوان مطلقة لكل الأوتار.
لإيجاد أضلاع \(G\) دون اختبار جميع الأزواج \(\binom{n}{2}\)، تُمسح الأوتار مرتبةً حسب الطرف الأيسر بينما تحتفظ مجموعة مرتبة بالأوتار المفتوحة حاليًا مُفتَّحةً حسب الطرف الأيمن. عندما يُفتح الوتر \([\ell,r]\)، فإن الأوتار التي تتقاطع معه هي بالضبط الأوتار المفتوحة التي يقع طرفها الأيمن في الفترة \((\ell,r)\): فقد بدأت قبل \(\ell\) وتنتهي بدقة بين \(\ell\) و\(r\). يعيدها استعلام مجال على المجموعة المرتبة، ويُتَّحد كل منها مع الوتر الحالي في بنية التكافؤ قبل إدراج \([\ell,r]\) نفسه. لذا يُعدّد المسح بدقة الأزواج المتقاطعة.
الفترة الصارمة \((\ell,r)\) مهمة. فالوتر السابق الذي يكون طرفه الأيمن \(\le \ell\) منفصل أصلًا عن الوتر الحالي، لذلك يتجاوزه استعلام المجال. والوتر السابق الذي يكون طرفه الأيمن \(\ge r\) يحتوي الوتر الحالي، فهو متداخل لا متقاطع. وبما أن كل موضع في المصفوفة طرف متميز، فإن حالة التقاطع الوحيدة الباقية هي بالضبط \(\ell \lt \text{right} \lt r\)، وهذا هو المجال الذي تعدّده المجموعة المرتبة.
القيمة \(0\) عند الموضعين \(0,4\)؛ والقيمة \(1\) عند \(1,3\)؛ والقيمة \(2\) عند \(2,5\). الأوتار هي \([0,4]\) و\([1,3]\) و\([2,5]\). هنا \([1,3]\) متداخل داخل \([0,4]\) (لا تقاطع)، بينما \([2,5]\) يتقاطع مع كل من \([0,4]\) و\([1,3]\). مخطط التقاطع هو مسار وحيد على ثلاثة رؤوس، بصنفَي لون \(\{[2,5]\}\) و\(\{[0,4],[1,3]\}\). ووضع الصنف الأكبر في الأعلى يعطي \(\max(1,2)=2\) وصلة فوقية، وهو الجواب المذكور.
تتشارك تطبيقات C++ وPython وJava خط المعالجة نفسه. تسجّل build_intervals الظهور الأول والثاني لكل قيمة، وتكوّن الأوتار، وترتّبها حسب الطرف الأيسر. وتختبر crosses شرط التشابك.
تنفّذ بنية ParityDsu اتحاد-إيجاد الموزون: تجري find ضغط المسار مع طيّ التكافؤ إلى الجذر، وتدمج unite حسب الحجم وتُبلغ عن تعارض (دورة فردية) عندما يصل ضلع متقاطع بين وترين بلون متساوٍ، وتعيد best_sum القيمة \(\sum\max(c_0,c_1)\)، وتعدّ component_count الجذور. وتشغّل solve_array مسح المجموعة المرتبة، فتتحد كل زوج متقاطع وتتوقف فور أن يثبت أن المخطط غير ثنائي.
مسار التحقق شامل على المدخلات الصغيرة: تسرد brute_force_array الأضلاع المتقاطعة وتجرّب جميع تعيينات الفوق/التحت البالغة \(2^n\)، محتفظةً بأكبر عدد فوقي صحيح، وتولّد validate_all_words كل مصفوفة طولها \(2n\) لأجل \(n\le 4\) وتتحقق من أن الحلّال السريع يتفق مع القوة الغاشمة في الثنائية والقيمة المثلى وعدد التقاطعات. وتثبّت run_checkpoints إضافةً إلى ذلك الحالات الصغيرة \([0,1,2,1,0,2]\mapsto 2\) و\([0,0,1,1,2,2]\mapsto 3\) والحالة غير الثنائية \([0,1,2,0,1,2]\)؛ ثم تحلّ main الحالة الكاملة.
ليكن \(C\) عدد الأزواج المتقاطعة الموجودة فعليًا. يكلّف بناء الأوتار وترتيبها \(O(n\log n)\)؛ ويجري المسح \(O(n+C)\) عملية على المجموعة المرتبة كلٌّ منها بـ \(O(\log n)\) و\(O(n+C)\) عملية اتحاد-إيجاد شبه ثابتة، ليكون الإجمالي
$$O\bigl((n+C)\log n\bigr)$$
زمنًا و\(O(n)\) ذاكرةً. على مدخل قابل للوصل الثنائي، يزور المسح الأضلاع المتقاطعة بالضبط بدلًا من جميع الأزواج \(\binom{n}{2}\). أما مدقّق القوة الغاشمة فأُسّي، \(O(2^n)\)، ولا يعمل إلا على مصفوفات التحقق الصغيرة جدًا.