Тема: корневая декомпозиция

В общем, есть задача, дан массив целых чисел и нужно, для каждого запроса надо отвечать сколько различных чисел на подмассиве, допустим для массива 1 2 1 3 2, для запроса 2 5 - ответ 3(3 различных числа), проблема вот в чём, все числа массива до 1000000000, более формально задаются вопросы так: На первой строке длина массива n < 300000. Потом сам массив. Кол-во запросов q < 300000. сами запросы по два числа(границы) Вот мой код:

#include <bits/stdc++.h>
using namespace std;
struct Query {
    int l, r, index;
};
bool compare(const Query &a, const Query &b, int block_size) {
    if (a.l / block_size == b.l / block_size) {
        return (a.l / block_size) % 2 == 0 ? a.r < b.r : a.r > b.r;
    }
    return a.l < b.l;
}
void add(int x, vector<int> &count, int &current_answer) {
    if (count[x] == 0) {
        current_answer++;
    }
    count[x]++;
}
void remove(int x, vector<int> &count, int &current_answer) {
    if (count[x] == 1) {
        current_answer--;
    }
    count[x]--;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int q;
    cin >> q;
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--;
        queries[i].r--;
        queries[i].index = i;
    }
    int MAX_VALUE = *max_element(arr.begin(), arr.end());
    vector<int> count(MAX_VALUE + 1, 0);
    int block_size = sqrt(n);
    sort(queries.begin(), queries.end(),
         [&block_size](Query &a, Query &b) { return compare(a, b, block_size); });
    vector<int> answers(q);
    int current_answer = 0;
    int current_l = 0, current_r = -1;
    for (const auto &query : queries) {
        while (current_r < query.r) add(arr[++current_r], count, current_answer);
        while (current_r > query.r) remove(arr[current_r--], count, current_answer);
        while (current_l < query.l) remove(arr[current_l++], count, current_answer);
        while (current_l > query.l) add(arr[--current_l], count, current_answer);
        answers[query.index] = current_answer;
    }
    for (int i = 0; i < q; i++) {
        cout << answers[i] << "\n";
    }
}

В нём я применяю алгоритм - МО(обрабатываю запросы в оффлайне) У него бывает переполнение, когда максимальное, число большое(например, 1e9) Если код писать с unordered_map, то код будет работать долго Помогите, пожалуйста! реализация с unordered_map

#include <bits/stdc++.h>
using namespace std;

struct Query {
    int l, r, index;
};

bool compare(const Query &a, const Query &b, int block_size) {
    if (a.l / block_size == b.l / block_size) {
        if ((a.l / block_size) % 2 == 0) {
            return a.r > b.r;
        } else {
            return a.r < b.r;
        }
    } else {
        return a.l < b.l;
    }
}

void add(int x, unordered_map<int, int> &count_map, int &current_answer) {
    count_map[x]++;
    if (count_map[x] == 1) {
        current_answer++;
    }
}

void remove(int x, unordered_map<int, int> &count_map, int &current_answer) {
    if (count_map[x] == 1) {
        current_answer--;
    }
    count_map[x]--;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int q;
    cin >> q;

    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].l--;  // переводим в 0-индексацию
        queries[i].r--;
        queries[i].index = i;
    }
    int block_size = sqrt(n);
    sort(queries.begin(), queries.end(),
         [&block_size](Query &a, Query &b) { return compare(a, b, block_size); });

    vector<int> answers(q);
    unordered_map<int, int> count_map;
    int current_answer = 0;
    int current_l = 0, current_r = -1;

    for (const auto &query : queries) {
        while (current_r < query.r)
            add(arr[++current_r], count_map, current_answer);
        while (current_r > query.r)
            remove(arr[current_r--], count_map, current_answer);
        while (current_l < query.l)
            remove(arr[current_l++], count_map, current_answer);
        while (current_l > query.l)
            add(arr[--current_l], count_map, current_answer);

        answers[query.index] = current_answer;
    }

    for (int i = 0; i < q; i++) {
        cout << answers[i] << "\n";
    }

    return 0;
}