Anpassen eines Segments in einer zweidimensionalen Ebene
Ich habe Probleme mit dem folgenden Problem
Gegebene N x S Segmente und m Segmente parallel zur horizontalen Achse (alle sind Tupel (x ', x' ', y) <) / em>), beantworte Q Online-Abfragen der Form (x ', x' ') . Die Antwort auf eine solche Abfrage ist das kleinste y (falls es eins gibt), so dass wir ein Segment (x ', x' ', y) platzieren können. Alle Segmente sind nicht überlappend, aber der Anfang eines Segments kann das Ende eines anderen sein, d. H. Segmente (x ', x' ', y) und (x' ', x' '', y) sind erlaubt. Die Möglichkeit, ein Segment zu platzieren, bedeutet, dass ein Segment (x ', x' ', y) existieren könnte, das die angegebenen Regeln nicht verletzt, das Segment nicht tatsächlich platziert wird (Board mit Anfangssegmenten wird nicht modifiziert), aber wir geben nur an da könnte einer sein.
Einschränkungen
%Vor% 
Hier ist ein Beispiel aus dem folgenden Link. Eingabesegmente sind (2, 5, 1), (1, 2, 2), (4, 5, 2), (2, 3, 3), (3, 4, 3).
Antwort für Fragen
1) (1, 2) → 1
2) (2, 3) → 2
3) (3, 4) → 2
4) (4, 5) → 3
5) (1, 3) → kann kein Segment
platzierenEine visualisierte Antwort für die dritte Abfrage (blaues Segment):
Ich verstehe nicht ganz, wie ich das Problem angehen soll. Es soll mit hartnäckigen Segmentbaum gelöst werden, aber ich bin immer noch nicht in der Lage, etwas zu finden.
Könnten Sie mir bitte helfen?
Das ist nicht meine Hausaufgabe. Das Quellproblem kann hier Ссылка gefunden werden. Es gibt keine englische Version der Anweisung, und der Testfall präsentiert die Eingabedaten auf andere Weise, also kümmern Sie sich nicht um die Quelle.
2 Antworten
Hier ist eine O (N log N) Zeitlösung.
Vorbemerkungen (ein gutes Tutorial hier ): Segmentbaum, persistenter Segmentbaum.
Teil 0. Ursprüngliche Problemstellung
Ich beschreibe die ursprüngliche Problemstellung kurz, da ich später in ihren Begriffen und nicht in abstrakten Segmenten sprechen werde.
Es gibt einen Zug mit S Sitzen (S & lt; = 10 ^ 5). Es ist bekannt, daß der Sitz s_i von der Zeit l_i bis zur Zeit r_i besetzt ist (nicht mehr als 10 ^ 5 solcher Beschränkungen oder Passagiere). Dann müssen wir 10 ^ 5 Anfragen von Art beantworten "finden Sie die niedrigste Zahl eines Sitzes mit ist frei von der Zeit l_i zu Zeit r_i oder sagen Sie, wenn es keine gibt". Alle Abfragen müssen online beantwortet werden, dh Sie müssen die vorherige Abfrage beantworten, bevor Sie die nächste abfragen.
Im ganzen Text bezeichne ich mit N sowohl die Anzahl der Sitze als auch die Anzahl der Passagiere und die Anzahl der Anfragen, vorausgesetzt, sie sind in der gleichen Größenordnung. Sie können bei Bedarf genauere Analysen durchführen.
Teil 1. Beantworten einer einzelnen Abfrage
Lassen Sie uns eine Abfrage [L, R] beantworten unter der Annahme, dass es nach der Zeit R keine besetzten Plätze gibt. Für jeden Platz behalten wir das letzte Mal bei, wenn es besetzt ist. Ruf es zuletzt an (S). Jetzt ist die Antwort für die Abfrage minimal S wie last (S) & lt; = L. Wenn wir einen Segmentbaum auf Plätzen bauen, können wir diese Abfrage in O (log ^ 2N) Zeit beantworten: binäre Suche der Wert von S, überprüfen, ob der Bereichsminimum auf Segment [0, S] höchstens L ist.
Allerdings reicht es möglicherweise nicht aus, Akzeptiert zu werden. Wir brauchen O (log N). Erinnern Sie sich daran, dass jeder Knoten eines Segmentbaums ein Minimum im entsprechenden Bereich speichert. Wir beginnen an der Wurzel. Wenn das Minimum dort & gt; = L ist, dann gibt es keinen Platz für eine solche Abfrage. Ansonsten ist entweder das Minimum im linken Kind oder im rechten Kind & lt; = L (oder in beiden). Im ersten Fall steigen wir zum linken Kind, in der zweiten - nach rechts, und wiederholen, bis wir ein Blatt erreichen. Dieses Blatt entspricht dem minimalen Sitz mit dem letzten (S) & lt; = L.
Teil 2. Lösen des Problems
Wir haben auf den Sitzen einen beständigen Baum, in dem wir die letzte (S) für jeden Sitz aufbewahren (wie im vorherigen Teil). Lassen Sie uns anfängliche Passagiere nacheinander nach ihrem linken Endpunkt in aufsteigender Reihenfolge sortieren. Für einen Passagier (s_i, l_i, r_i) aktualisieren wir den Segmentbaum an der Position s_i mit dem Wert r_i. Der Baum ist persistent, also speichern wir die neue Kopie irgendwo.
Um eine Abfrage [L, R] zu beantworten, suchen Sie eine aktuelle Version des Segmentbaums, so dass die Aktualisierung vor R erfolgte. Wenn Sie eine binäre Suche nach Versionen durchführen, dauert die O (log N) -Zeit.
In der Version des Segmentbaums sind nur Passagiere mit ihrem linken Endpunkt & lt; R werden berücksichtigt (noch mehr, genau solche Passagiere sind). Daher können wir den Algorithmus aus Teil 1 verwenden, um die Abfrage mithilfe dieses Segmentbaums zu beantworten.
Aussage:
Eingabe: list<x',x'',Y>
Abfrageeingabe: (X',X'')
Ausgabe: Ymin
Einschränkungen:
%Vor%Antwort:
Datenstrukturmethode, die Sie verwenden können:
1. Brute force : Iteriere direkt durch die Liste und führe die Überprüfung durch.
2. Sortieren : Sortieren Sie die Liste in Y [niedrigste bis höchste] und durchlaufen Sie sie anschließend.
Hinweis: Das Sortieren großer Listen ist zeitaufwendig.
%Vor% 3. Hashmap : Map<Y, list< tuple<x',length> > > , um eine Liste von Zeilen für jede Y zu speichern und durch sie zu durchlaufen, um mindestens Y zu erhalten.
Hinweis: benötigt zusätzliche Zeit für die Erstellung der Map.
%Vor%4. Matrix : Sie können eine Matrix mit 1 für einen belegten Punkt und 0 für einen leeren Punkt erstellen.
Hinweis: benötigt zusätzliche Zeit für den Matrix-Build, und die Iteration durch die Matrix ist zeitaufwendig und daher nicht sinnvoll.
Beispiel:
%Vor%Tags und Links algorithm data-structures segment-tree persistent-data