различные числа (Мо)

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <stdio.h>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <iterator>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <array>
//#define int long long
#define pb push_back
#define fir first
#define sec second
#define double long double
#define endl "\n"
#define un unsigned
#define INF 1000000000009
#define EPS 0.000000000001
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1000009, R = 1 << 20, logn = 19, ABC = 26, BUBEN = 350;

struct S {
    int first, second, id;
    S(int a, int b, int c) : fir(a), sec(b), id(c) {}
    S() {}
};

bool cmp(S a, S b) {
    if (a.first / BUBEN == b.first / BUBEN)
        return a.second < b.second;
    return a.first < b.first;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> vc(n);

    for (int& i : vc)
        cin >> i;

    vector<int> a = vc;
    sort(all(a));
    a.erase(unique(all(a)), a.end());

    for (int i = 0; i < n; i++)
        vc[i] = lower_bound(all(a), vc[i]) - a.begin();

    int q;
    cin >> q;

    vector<S> query(q);
    int id = 0;
    for (auto& i : query) {
        cin >> i.first >> i.second;
        i.id = id;
        id++;
    }
    sort(all(query), cmp);

    int pr = -1;
    int ll = -1, rr = -1;
    vector<int> cnt(a.size());
    vector<int> ans(q);
    int answer = 0;
    for (int i = 0; i < q; i++) {
        int l = query[i].first, r = query[i].second;
        l--;
        r--;
        if (pr == -1) {
            for (int j = l; j <= r; j++) {
                cnt[vc[j]]++;
                if (cnt[vc[j]] == 1)
                    answer++;
            }
            ll = l;
            rr = r;
            pr = 0;
        }
        else {
            while (ll > l) {
                ll--;
                cnt[vc[ll]]++;
                if (cnt[vc[ll]] == 1)
                    answer++;
            }
            while (rr < r) {
                rr++;
                cnt[vc[rr]]++;
                if (cnt[vc[rr]] == 1)
                    answer++;
            }

            while (ll < l) {
                cnt[vc[ll]]--;
                if (cnt[vc[ll]] == 0)
                    answer--;
                ll++;
            }
            while (rr > r) {
                cnt[vc[rr]]--;
                if (cnt[vc[rr]] == 0)
                    answer--;
                rr--;
            }
        }
        ans[query[i].id] = answer;
    }
    for (int i : ans)
        cout << i << endl;
    return 0;
}