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

Question

[ChastIOtvaga]

Помогите с решение ошибки 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; 
}

Answer 1

[Wataru]

Ваше решение медленно считает сумму на отрезке. За O(n) - вы проходитесь по всему множеству. А все ваше рение будет O(n^2). Когда как это надо делать за O(log n) максимум. Ну посмотрите же на ограничения - n <= 10^5. Обычно n^2 работает ну до 10^4 максимум с огромным скрипом и натяжками.

К сожалению, стандартными set'ами вы сумму на отрезке быстро не подсчитаете. Придется реализовывать сбалансированное бинарное дерево поиска, где в каждой вершине надо дополнительно хранить сумму всех значений в поддереве. Вот реализация дерева, но там сумма на отрезке не реализована. Однако, в статье расказанно, как это делать. Ищите на странице "на отрезке".

Если бы числа в задаче был поменьше, то можно было бы использовать дерево отрезков. Это сильно проще реализуется. Но тут бы это потребовало массивы на 2*10^9 элементов.

Edit: вообще, судя по нескольким вопросам от вас, у вас там задачи именно на реализацию бинарных деревьев поиска с дополнительными данными в вершинах. Вот если у вас следующая задача опять не пройдет по времени, то сначала убедитесь, что вы используете собственноручно написанное дерево поиска.

Comments

[ChastIOtvaga]

вот попробовал реализовать через бинарное дерево но не проходит тест :

Sample Input:

15
? 1
+ 1
? 1
+ 2
s 1 2
+ 1000000000
? 1000000000
- 1000000000
? 1000000000
s 999999999 1000000000
- 2
? 2
- 0
+ 9
s 0 9

Sample Output:

Not found
Found
3
Found
Not found
1
Not found
10

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int val) {
        this->val = val;
        left = right = NULL;
    }
};

void insert(Node*& root, int val) {
    if (root == NULL) {
        root = new Node(val);
    }
    else if (val < root->val) {
        insert(root->left, val);
    }
    else if (val > root->val) {
        insert(root->right, val);
    }
}

bool find(Node* root, int val) {
    if (root == NULL) {
        return false;
    }
    else if (val == root->val) {
        return true;
    }
    else if (val < root->val) {
        return find(root->left, val);
    }
    else {
        return find(root->right, val);
    }
}

Node* findMin(Node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

void remove(Node*& root, int val) {
    if (root == NULL) {
        return;
    }
    else if (val < root->val) {
        remove(root->left, val);
    }
    else if (val > root->val) {
        remove(root->right, val);
    }
    else if (root->left != NULL && root->right != NULL) {
        root->val = findMin(root->right)->val;
        remove(root->right, root->val);
    }
    else {
        Node* oldNode = root;
        root = (root->left != NULL) ? root->left : root->right;
        delete oldNode;
    }
}

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

    Node* root = NULL;

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

        if (op == '+') {
            insert(root, val);
        }
        else if (op == '-') {
            remove(root, val);
        }
        else if (op == '?') {
            if (find(root, val)) {
                cout << "Found" << endl;
            }
            else {
                cout << "Not found" << endl;
            }
        }
    }

    return 0;
}

[Wataru]

ChastIOtvaga, ээээм. Посмотрите на ваш код в вопросе в main. Посмотрите на этот код. Никакой разницы не видите? После копипастентч кода надо его хоть разок прочитать-то перел отправкой.

И вообще, у вас тест есть. С нужным выводом. Запустите локально и отдебажте.

[Wataru]

ChastIOtvaga, и дерево у вас не сбалансированное - упадет по тайм лимиту. И сумму в поддереве вы не реализовали.