Treap для запросов и добавлений

Einführung der Aufgabenstellung

Ich beginne damit, die Familienmitglieder mit den angegebenen Stimmungen zu begrüßen. Nach der Begrüßung berechne ich die Summe der Stimmungen der Familienmitglieder in den angegebenen Zeitfenstern.

Befehle verstehen

Ich bin dabei, die Funktionsweise der Befehle "+ i" und "? l r" zu klären. "+ i" fügt direkt hinzu, "["?" ?>" "]" verwendet für Additionen basierend auf vorherigen Ergebnissen. Einschränkungen finden Platz, wie hier beschrieben.

Erstellen eines kartesischen Baums

Ich analysiere den Code, um einen kartesischen Baum zu erstellen, der Eigenschaften von Fahrzeugen enthält. Die Struktur Node speichert Indizes und Elternknoten. Die Funktion buildCartesianTree setzt Eltern- und Kindbeziehungen durch stackbasierte Operationen.

Verbudene Strukturen

Es wird darauf hingewiesen, dass keine eingebauten Strukturen wie map oder set verwendet werden dürfen. Der Code kann als Hinweis dienen.

Ich sehe, dass wir ein Problem behandeln, bei dem es um das Hinzufügen und Abfragen von Familienmitgliedern mit bestimmten Stimmungen geht. Nach einem Abfrageergebnis könnte ein Hinzufügen angepasst werden.

Überlegen und strukturieren

Ich denke darüber nach, wie ich eine Struktur implementieren kann, um Stimmungen effizient zu verarbeiten, dabei den Einsatz von eingebauten Maps oder Sets vermeide. Eine selbstimplementierte balancierte Suchbaum-Datenstruktur oder ein Segmentbaum werden als mögliche Lösungen betrachtet.

Suchen nach Alternativen

Aufgrund der großen Werte möchte ich nicht direkt jeden einzelnen Wert verarbeiten. Ich denke darüber nach, einen eigens entwickelten Segmentbaum zu erstellen, ohne eingebaute Strukturen wie Map oder Set zu verwenden.

Mithilfe des Segmentbaums

Interessant, wie Sie den Bedarf an Speicherplatz minimieren, indem Sie ein Segmentbaum-Array nutzen und eine Trie-Struktur für die Werte implementieren. Dadurch bleibt die Arbeit mit den Werten im Bereich [0, 1e9] effizient.

Erstellen eines besonderen Baums

Ich denke darüber nach, wie man einen speziellen Baum baut, der Zahlen einfügt, duplizierte Werte vermeidet und Summen bis zu einem Punkt berechnet.

Entwickeln eines Treaps

Ich denke darüber nach, wie der Wurzelbaum als binärer Suchbaum gestaltet wird, um Einfügen und Abfragen effizient zu ermöglichen.

Spannende Überlegungen

Ich schaue mir an, wie eine + i-Operation nach einer ?-Abfrage verändert wird und wie wir den letzten Abfrageergebniswert nachverfolgen.

Entwicklung eines Treap

Ich bin gerade dabei, einen Treap in C++ zu schreiben, indem ich die Struktur der Knoten mit Schlüsseln, Prioritäten, Kinderzeigern und Teilbaum-Summen entwerfe. Die Einfüge- und Abfrageoperationen gemäß BST und Treap-Urgestein sind geplant.

Merging und Aufteilen

Ich denke darüber nach, wie man ein Treap in linke und rechte Teile aufteilen kann und dann sie wieder zusammenführt. Diese Techniken helfen bei der Einfüge- und Abfragefunktion, ohne Duplikate zuzulassen.

Entwurf und Implementierung

Ich beginne, die Struktur des Knotens zu definieren: Schlüssel, Priorität, Summe der Schlüssel im Unterbaum und Zeiger auf linke und rechte Kinder. Ich aktualisiere auch die Summe, wenn Kinder geändert werden.

Verheilung einer Aufgabe

Umstrukturierung und Merge

Ich erstatte dem Baumlaufwerk treap, indem ich die Einfügefunktion durch Split und Merge ersetze, um weniger Arbeitsspeicher zu verwenden.

Einfügungslogik

Ich schaue mir an, wie die Einfügefunktion den Baum organisiert, indem sie Knoten vergleicht und teilenteilweise Wurzeln setzt, um Prioritäten zu ordnen und Duplikate zu vermeiden.

Methode der Treap-Split

Ich denke darüber nach, wie ich die Treap in drei Teile aufteilen kann: links für Schlüssel < l, mitte für Schlüssel [l, r], und rechts für Schlüssel > r. Die Summe kommt aus der mittleren Treap.

Ändern des Wurzels

Ich zerteile den Treap, um Bereiche zu extrahieren, deren Werte ich summiere und dann wieder zusammenfüge. Schwierigkeiten könnten in der Handhabung von Einsätzen und deren Kombination stecken.

Bearbeiten von Operationen

Ich fange mit ? l r an, lese l und r, berechne y und gebe y aus. Dann gehe ich zu + i, lese i, modifiziere es und füge es in den treap ein.

Verstehe die Operationen

Ich denke darüber nach, wie der Wert von y das Verhalten der Operation beeinflusst. Wenn das letzte Zeichen '+' ist, wird einfach add(i) ausgeführt. Wenn das letzte Zeichen '?' war, wird add((i + y) mod 1e9) ausgeführt.

Verfolge den Verlauf

Ich suche nach einer Methode, um die vorherige Operation zu berücksichtigen und diese in Echtzeit zu verarbeiten.

Vorausschauend berechnen

Ich beobachte das Setzen von Operationsleitungen und identifiziere die Unterschiede zwischen fragen und hinzufügen, um Berechnungen effizient zu gestalten.

Implementierung der Operationen

Ich zeige, wie '? l r' Operationen das Ergebnis von vorherigen Additionsoperationen beeinflussen. Um konsistent mit den Eingabemodifikationen zu bleiben, prüfe ich 'prevWasQuery'.

Klärung der Operationen

Ich schaue mir die Problemstellung an und stelle fest, dass Modulo-Operationen nur auf die 'i' bei 'add'-Operationen nach einer Abfrage angewendet werden. Also, l und r werden direkt gelesen.

Bearbeite Operationen

Ich denke gerade darüber nach, wie wir die Operationen nahtlos verarbeiten und dabei Überläufe richtig handhaben können.

Überprüfung der Überlegungen

Ich denke darüber nach, ob beim Modulo 1e9 die Werte von 0 bis 1e9 eingeschlossen sind und prüfe, ob das verwenden eines lange long (64-bit Integer) für die Summe akzeptabel ist.

Modulo-Verwaltung bei großen Zahlen

Überlegungen zur Modulusberechnung

Ich denke darüber nach, wie man (i + y) % (1e9 + 1) berechnet und erwäge dabei, ob man stattdessen mod 1e9 verwenden sollte.

Optimieren des Codes

OK, lasst uns den Code anpassen und minimal modifizieren. Ein deterministischer RNG funktioniert gut, und '\n' anstelle von std::endl scheint klug.

Erstellen einer Zufallszahlengeneratorinstanz

Ich starte mit der Definition einer Zufallszahlengeneratorinstanz, die für die Priorisierung im Knoten einfacher ist. Besonders interessante Queries werden durch diesen Mechanismus unterstützt.

To solve this problem efficiently without using built-in map, set, or similar data structures, we can implement our own balanced binary search tree (BST). Specifically, we will use a treap (a randomized BST), which allows us to perform insertions and range sum queries in $O(\log n)$ time.

Here's the step-by-step approach:

1. Understand the Problem Constraints:

   • We need to support two operations: adding a unique mood value and querying the sum of mood values within a range.
   • We have to handle up to $3 \times 10^5$ operations.
   • Mood values range from $0$ to $10^9$.

2. Implement a Treap:

   • A treap combines the properties of a binary search tree and a heap.
   • Each node contains a key (mood value), a priority (for balancing), and the sum of the subtree.
   • We need to implement split, merge, insert, and query functions.

3. Handle Duplicate Keys:

   • Since we cannot have duplicate mood values, we need to check if a key already exists before inserting.
   • If a key exists, we skip the insertion.

4. Process Operations According to Rules:

   • Maintain a variable y to store the result of the last query.
   • If an add operation comes after a query, adjust the mood value using (i + y) % 10^9.
   • For queries, we directly use the provided l and r values.

5. Efficient Input/Output:

   • Use '\n' instead of std::endl to avoid flushing the output buffer, which can slow down the program.
   • Use scanf and printf for faster I/O if necessary.

6. Random Number Generation:

   • Seed the random number generator to ensure the treap is balanced.
   • Use std::mt19937 with a seed based on the current time.

Below is the complete C++ code implementing the above approach:

#include <iostream>
#include <random>
#include <chrono>

struct Node {
    int key; // mood value
    int priority;
    long long sum; // sum of keys in subtree
    Node *left, *right;

    Node(int key, int priority) : key(key), priority(priority), sum(key), left(nullptr), right(nullptr) {}
};

void update(Node* node) {
    if (node) {
        node->sum = node->key;
        if (node->left) node->sum += node->left->sum;
        if (node->right) node->sum += node->right->sum;
    }
}

void split(Node* root, int key, Node* &left, Node* &right) {
    if (!root) {
        left = right = nullptr;
    } else if (key <= root->key) {
        split(root->left, key, left, root->left);
        right = root;
    } else {
        split(root->right, key, root->right, right);
        left = root;
    }
    update(root);
}

Node* merge(Node* left, Node* right) {
    if (!left || !right)
        return left ? left : right;
    if (left->priority > right->priority) {
        left->right = merge(left->right, right);
        update(left);
        return left;
    } else {
        right->left = merge(left, right->left);
        update(right);
        return right;
    }
}

void insert(Node* &root, Node* node) {
    if (!root) {
        root = node;
    } else if (node->key == root->key) {
        delete node; // key already exists, avoid duplicates
        return;
    } else if (node->priority > root->priority) {
        split(root, node->key, node->left, node->right);
        root = node;
    } else if (node->key < root->key) {
        insert(root->left, node);
    } else {
        insert(root->right, node);
    }
    update(root);
}

void insert(Node* &root, int key, int priority) {
    insert(root, new Node(key, priority));
}

long long query(Node* &root, int l, int r) {
    Node *t1 = nullptr, *t2 = nullptr, *t3 = nullptr;
    split(root, l, t1, t2);
    split(t2, r + 1, t2, t3);
    long long res = t2 ? t2->sum : 0;
    root = merge(t1, merge(t2, t3));
    return res;
}

int main() {
    int n;
    std::cin >> n;
    Node* root = nullptr;
    long long y = 0;
    bool prevWasQuery = false;

    std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

    for (int idx = 0; idx < n; ++idx) {
        char op;
        std::cin >> op;
        if (op == '+') {
            long long i;
            std::cin >> i;
            if (prevWasQuery) {
                i = (i + y) % 1000000000;
            }
            insert(root, (int)i, rng());
            prevWasQuery = false;
        } else if (op == '?') {
            int l, r;
            std::cin >> l >> r;
            y = query(root, l, r);
            std::cout << y << "\n";
            prevWasQuery = true;
        }
    }
    return 0;
}

Explanation:

• Node Structure:

  • Each node stores the key, priority, sum, and pointers to left and right children.
  • The sum is updated every time the tree is modified to ensure range queries are efficient.

• Insert Function:

  • Uses split and merge to insert a new node while maintaining the treap properties.
  • Checks for duplicates and avoids inserting the same key twice.

• Query Function:

  • Splits the treap into three parts to isolate the range [l, r].
  • Retrieves the sum from the middle part and then merges the treap back.

• Main Function:

  • Processes each operation according to the rules.
  • Maintains the prevWasQuery flag to adjust the mood value for add operations following a query.
  • Outputs the result of each query.

Note:

• Randomness:

  • We seed the random number generator with the current time to ensure the treap is balanced.
  • This avoids worst-case scenarios that can degrade performance.

• Efficiency:

  • Using custom data structures and avoiding unnecessary flushing of the output stream ensures the program runs within the time limits.

This solution adheres to the problem constraints and efficiently processes all operations without using prohibited built-in data structures.