@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; 
}
  • Вопрос задан
  • 257 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Ваше решение медленно считает сумму на отрезке. За O(n) - вы проходитесь по всему множеству. А все ваше рение будет O(n^2). Когда как это надо делать за O(log n) максимум. Ну посмотрите же на ограничения - n <= 10^5. Обычно n^2 работает ну до 10^4 максимум с огромным скрипом и натяжками.

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы