Множество с запросами

[ChestIotVaga]

Помогите с решение ошибки Failed test #69 of 83. Time limit exceeded
Реализуйте структуру данных для хранения множества целых чисел,
поддерживающую запросы добавления, удаления, поиска, а также
суммы на отрезке. На вход в данной задаче будет дана последовательность таких запросов. Чтобы гарантировать, что ваша программа
обрабатывает каждый запрос по мере поступления (то есть онлайн),
каждый запрос будет зависеть от результата выполнения одного из
предыдущих запросов. Если бы такой зависимости не было, задачу
можно было бы решить оффлайн: сначала прочитать весь вход и сохранить все запросы в каком-нибудь виде, а потом прочитать вход
ещё раз, параллельно отвечая на запросы.
Формат входа. Изначально множество пусто. Первая строка содержит число запросов n. Каждая из n следующих строк содержит
запрос в одном из следующих четырёх форматов:
• + i: добавить число f(i) в множество (если оно уже есть,
проигнорировать запрос);
• - i: удалить число f(i) из множества (если его нет, проигнорировать запрос);
• ? i: проверить принадлежность числа f(i) множеству;
• s l r: посчитать сумму всех элементов множества, попадающих в отрезок [f(l), f(r)].
Функция f определяется следующим образом. Пусть s — результат последнего запроса суммы на отрезке (если таких запросов
ещё не было, то s = 0). Тогда
f(x) = (x + s) mod 1 000 000 001 .
Формат выхода. Для каждого запроса типа ? i выведите «Found»
или «Not found». Для каждого запроса суммы выведите сумму
всех элементов множества, попадающих в отрезок [f(l), f(r)]. Гарантируется, что во всех тестах f(l) ≤ f(r).
Ограничения. 1 ≤ n ≤ 105
; 0 ≤ i ≤ 109

#include <iostream> 
#include <unordered_set> 
 
using namespace std; 
 
const int MOD = 1000000001; 
 
int main() { 
    int n, s = 0; 
    cin >> n; 
 
    unordered_set<int> st; 
    while (n--) { 
        char op; 
        int x, l, r; 
        cin >> op >> x; 
        if (op == '+') { 
            x = (x + s) % MOD; 
            if (st.find(x) == st.end()) st.insert(x); 
        } else if (op == '-') { 
            x = (x + s) % MOD; 
            if (st.find(x) != st.end()) st.erase(x); 
        } else if (op == '?') { 
            x = (x + s) % MOD; 
            if (st.find(x) != st.end()) cout << "Found\n"; 
            else cout << "Not found\n"; 
        } else { 
            cin >> r; 
            l = x; 
            x = (l + s) % MOD; 
            r = (r + s) % MOD; 
            long long sum = 0; 
            for (auto it = st.begin(); it != st.end(); ++it) { 
                if (*it >= x && *it <= r) sum += *it; 
            } 
            cout << sum << '\n'; 
            s = sum % MOD; 
        } 
    } 
 
    return 0; 
}

[ChestIotVaga]

6.4 Множество с запросами суммы на отрезке
Реализуйте структуру данных для хранения множества целых чисел,
поддерживающую запросы добавления, удаления, поиска, а также
суммы на отрезке. На вход в данной задаче будет дана последова-
тельность таких запросов. Чтобы гарантировать, что ваша программа
обрабатывает каждый запрос по мере поступления (то есть онлайн),
каждый запрос будет зависеть от результата выполнения одного из
предыдущих запросов. Если бы такой зависимости не было, задачу
можно было бы решить оффлайн: сначала прочитать весь вход и со-
хранить все запросы в каком-нибудь виде, а потом прочитать вход
ещё раз, параллельно отвечая на запросы.
Формат входа. Изначально множество пусто. Первая строка содер-
жит число запросов n. Каждая из n следующих строк содержит
запрос в одном из следующих четырёх форматов:
• + i: добавить число f (i) в множество (если оно уже есть,
проигнорировать запрос);
• - i: удалить число f (i) из множества (если его нет, про-
игнорировать запрос);
• ? i: проверить принадлежность числа f (i) множеству;
• s l r: посчитать сумму всех элементов множества, попа-
дающих в отрезок [f (l), f (r)].
Функция f определяется следующим образом. Пусть s — резуль-
тат последнего запроса суммы на отрезке (если таких запросов
ещё не было, то s = 0). Тогда
f (x) = (x + s) mod 1 000 000 001 .
Формат выхода. Для каждого запроса типа ? i выведите «Found»
или «Not found». Для каждого запроса суммы выведите сумму
всех элементов множества, попадающих в отрезок [f (l), f (r)]. Га-
рантируется, что во всех тестах f (l) ≤ f (r).
Ограничения. 1 ≤ n ≤ 105; 0 ≤ i ≤ 109.
тесты :
Пример.
Вход:
15
? 1
+ 1
? 1
+ 2
s 1 2
+ 1000000000
? 1000000000
- 1000000000
? 1000000000
s 999999999 1000000000
- 2
? 2
- 0
+ 9
s 0 9
Выход:
Not found
Found
3
Found
Not found
1
Not found
10
Для первых пяти запросов s = 0, для следующих пяти — s = 3,
для следующих пяти — s = 1. Заданные запросы разворачива-
ются в следующие: find(1), add(1), find(1), add(2), sum(1, 2) → 3,
add(2), find(2) → Found, del(2), find(2) → Not found, sum(1, 2) → 1,
del(3), find(3) → Not found, del(1), add(10), sum(1, 10) → 10. Добав-
ление элемента дважды не изменяет множество, как и попытки
удалить элемент, которого в множестве нет
Пример.
Вход:
5
? 0
+ 0
? 0
- 0
? 0
Выход:
Not found
Found
Not found
Пример.
Вход:
5
+ 491572259
? 491572259
? 899375874
s 310971296 877523306
+ 352411209
Выход:
Found
Not found
491572259
Помогите с решение вот мой код:

#include <iostream>
#include <cstdlib>

using namespace std;

struct Node {
    int val, priority, size;
    Node* left, * right;

    Node(int val) : val(val), priority(rand()), size(1), left(nullptr), right(nullptr) {}
};

class Treap {
private:
    Node* root;

    void split(Node* node, int k, Node*& left, Node*& right) {
        if (node == nullptr) {
            left = nullptr;
            right = nullptr;
        }
        else if (node->val <= k) {
            split(node->right, k, node->right, right);
            left = node;
        }
        else {
            split(node->left, k, left, node->left);
            right = node;
        }
        update_size(node);
    }
    Node* merge(Node* left, Node* right) {
        if (left == nullptr) return right;
        if (right == nullptr) return left;

        if (left->priority > right->priority) {
            left->right = merge(left->right, right);
            update_size(left);
            return left;
        }
        else {
            right->left = merge(left, right->left);
            update_size(right);
            return right;
        }
    }

    int count(Node* node, int l, int r) {
        if (node == nullptr) return 0;
        if (node->val < l) {
            return count(node->right, l, r);
        }
        else if (node->val > r) {
            return count(node->left, l, r);
        }
        else {
            return node->size + count(node->left, l, r) + count(node->right, l, r);
        }
    }

    void update_size(Node* node) {
        if (node == nullptr) return;
        node->size = 1;
        if (node->left != nullptr) node->size += node->left->size;
        if (node->right != nullptr) node->size += node->right->size;
    }

public:
    Treap() : root(nullptr) {}
    void insert(int val) {
        if (find(val) == nullptr) {
            Node* new_node = new Node(val);
            Node* left, * right;
            split(root, val, left, right);
            root = merge(merge(left, new_node), right);
        }
    }

    void remove(int val) {
        Node* node = find(val);
        if (node != nullptr) {
            Node* left, * right, * del;
            split(root, val, left, right);
            split(right, val + 1, del, right);
            root = merge(left, right);
            delete del;
        }
    }

    Node* find(int val) {
        Node* curr = root;
        while (curr != nullptr) {
            if (val == curr->val) return curr;
            if (val < curr->val) curr = curr->left;
            else curr = curr->right;
        }
        return nullptr;
    }

    int sum(int l, int r, int s) {
        int fl = (l + s) % 1000000001;
        int fr = (r + s) % 1000000001;
        return count(root, fl, fr);
    }
};

int main() {
    int n;
    cin >> n;
    Treap treap;
    int s = 0;

    for (int i = 0; i < n; i++) {
        char op;
        int x;
        cin >> op >> x;

        if (op == '+') {
            treap.insert((x + s) % 1000000001);
        }
        else if (op == '-') {
            treap.remove((x + s) % 1000000001);
        }
        else if (op == '?') {
            if (treap.find((x + s) % 1000000001) != nullptr) {
                cout << "Found" << endl;
            }
            else {
                cout << "Not found" << endl;
            }
        }
        else if (op == 's') {
            int l, r;
            cin >> l >> r;
            cout << treap.sum(l, r, s) << endl;
        }

        s %= 1000000001;
    }

    return 0;

}

[BDA]

Вот так вроде работает:

#include <iostream>
#include <cstdlib>

using namespace std;

struct Node {
    int val, priority, size;
    Node* left, * right;

    Node(int val) : val(val), priority(rand()), size(1), left(nullptr), right(nullptr) {}
};

class Treap {
private:
    Node* root;
    int s;

    void split(Node* node, int k, Node*& left, Node*& right) {
        if (node == nullptr) {
            left = nullptr;
            right = nullptr;
        }
        else if (node->val <= k) {
            split(node->right, k, node->right, right);
            left = node;
        }
        else {
            split(node->left, k, left, node->left);
            right = node;
        }
        update_size(node);
    }
    Node* merge(Node* left, Node* right) {
        if (left == nullptr) return right;
        if (right == nullptr) return left;

        if (left->priority > right->priority) {
            left->right = merge(left->right, right);
            update_size(left);
            return left;
        }
        else {
            right->left = merge(left, right->left);
            update_size(right);
            return right;
        }
    }

    int count(Node* node, int l, int r) {
        if (node == nullptr) return 0;
        if (node->val < l) {
            return count(node->right, l, r);
        }
        else if (node->val > r) {
            return count(node->left, l, r);
        }
        else {
            return node->val + count(node->left, l, r) + count(node->right, l, r);
        }
    }

    void erase(Node*& node, int val) {
        if (node == nullptr) return;
        if (node->val == val) {
            Node* old_node = node;
            node = merge(node->left, node->right);
            delete old_node;
        } else
            erase(val < node->val ? node->left : node->right, val);
    }

    void update_size(Node* node) {
        if (node == nullptr) return;
        node->size = 1;
        if (node->left != nullptr) node->size += node->left->size;
        if (node->right != nullptr) node->size += node->right->size;
    }

public:
    Treap() : root(nullptr), s(0) {}

    int f(int val) {
        return (val + s) % 1000000001;
    }

    void insert(int val) {
        if (find(val) == nullptr) {
            Node* new_node = new Node(val);
            Node* left, * right;
            split(root, val, left, right);
            root = merge(merge(left, new_node), right);
        }
    }

    void remove(int val) {
        erase(root, val);
    }

    Node* find(int val) {
        Node* curr = root;
        while (curr != nullptr) {
            if (val == curr->val) return curr;
            curr = (val < curr->val) ? curr->left : curr->right;
        }
        return nullptr;
    }

    int sum(int l, int r) {
        s = count(root, l, r);
        return s;
    }
};

int main() {
    int n;
    cin >> n;
    Treap treap;

    for (int i = 0; i < n; i++) {
        char op;
        int x;
        cin >> op >> x;

        if (op == '+') {
            treap.insert(treap.f(x));
        }
        else if (op == '-') {
            treap.remove(treap.f(x));
        }
        else if (op == '?') {
            if (treap.find(treap.f(x)) != nullptr) {
                cout << "Found" << endl;
            }
            else {
                cout << "Not found" << endl;
            }
        }
        else if (op == 's') {
            int r;
            cin >> r;
            cout << treap.sum(treap.f(x), treap.f(r)) << endl;
        }
    }

    return 0;
}

Перенес s в поле класса, перенес преобразование числа в метод f, поправил опечатку size -> val в методе count (по идее опечатка), заменил метод remove (а то что-то не работал), убрал считывание l (ведь оно уже считано в x). В текущем виде поле size получается никак не используется.

[ChestIotVaga]

падает на 20 тесте а мне он не дан только вот как пример который я скинул
Failed test #20 of 83. Wrong answer

[ChestIotVaga]

почитав пару комментариев задачи ребята говорят проще через AVL дерево вот попробовал реализовать но там 3 ошибки помогите исправить -

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Node {
    int key;
    int sum;
    int height;
    Node* left;
    Node* right;

    Node(int k) {
        key = k;
        sum = k;
        height = 1;
        left = right = nullptr;
    }
};

int height(Node* p) {
    return p ? p->height : 0;
}

int balance_factor(Node* p) {
    return height(p->right) - height(p->left);
}

void fix_height(Node* p) {
    p->height = max(height(p->left), height(p->right)) + 1;
}

Node* rotate_right(Node* p) {
    Node* q = p->left;
    p->left = q->right;
    q->right = p;
    fix_height(p);
    fix_height(q);
    return q;
}

Node* rotate_left(Node* q) {
    Node* p = q->right;
    q->right = p->left;
    p->left = q;
    fix_height(q);
    fix_height(p);
    return p;
}

Node* balance(Node* p) {
    fix_height(p);
    if (balance_factor(p) == 2) {
        if (balance_factor(p->right) < 0)
            p->right = rotate_right(p->right);
        return rotate_left(p);
    }
    if (balance_factor(p) == -2) {
        if (balance_factor(p->left) > 0)
            p->left = rotate_left(p->left);
        return rotate_right(p);
    }
    return p;
}

Node* insert(Node* p, int k, int& s) {
    if (!p)
        return new Node(k);
    if (k == p->key)
        return p;
    if (k < p->key)
        p->left = insert(p->left, k, s);
    else
        p->right = insert(p->right, k, s);
    p = balance(p);
    fix_height(p);
    if (!p->left && !p->right)
        p->sum = p->key;
    else if (!p->left)
        p->sum = p->key + p->right->sum;
    else if (!p->right)
        p->sum = p->key + p->left->sum;
    else
        p->sum = p->key + p->right->sum + p->left->sum;
    s = p->sum;
    return p;
}

Node* remove(Node* p, int k, int& s) {
    if (!p)
        return 0;
    if (k < p->key)
        p->left = remove(p->left, k, s);
    else if (k > p->key)
        p->right = remove(p->right, k, s);
    else {
        Node* q = p->left;
        Node* r = p->right;
        delete p;
        if (!r)
            return q;
        Node* min = find_min(r);
        min->right = remove_min(r);
        min->left = q;
        return balance(min);
    }
    p = balance(p);
    fix_height(p);
    if (!p->left && !p->right)
        p->sum = p->key;
    else if (!p->left)
        p->sum = p->key + p->right->sum;
    else if (!p->right)
        p->sum = p->key + p->left->sum;
    else
        p->sum = p->key + p->right->sum + p->left->sum;
    s = p->sum;
    return p;
}

Node* find(Node* p, int k) {
    if (!p)
        return 0;
    if (k == p->key)
        return p;
    if (k < p->key)
        return find(p->left, k);
    else
        return find(p->right, k);
}

int main() {
    int n;
    cin >> n;
    Node* root = 0;
    int s = 0;
    for (int i = 0; i < n; ++i) {
        char c;
        int x;
        cin >> c >> x;
        if (c == '+') {
            x = (x + s) % 1000000001;
            insert(root, x, s);
        }
        else if (c == '-') {
            x = (x + s) % 1000000001;
            remove(root, x, s);
        }
        else if (c == '?') {
            x = (x + s) % 1000000001;
            cout << (find(root, x) ? "Found\n" : "Not found\n");
        }
        else {
            int y;
            cin >> y;
            x = (x + s) % 1000000001;
            y = (y + s) % 1000000001;
            if (x > y)
                swap(x, y);
            cout << sum(root, x, y) << endl;
        }
    }
    return 0;
}