Shared code

#include <bits/stdc++.h>
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << ": " << arg1 << "\t|";
    __f(comma + 1, args...);
}
 
#define print(x)           \
    for (auto it : x)      \
        cout << it << ' '; \
    cout << '\n';
#define mem1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define int long long
 
// typedef long long ll;
typedef unsigned long long ull;
 
const int N = 2e5 + 5;
const int BLOCK = 447;  // ~sqrt(N)
 
int a[N], ans[N], answer = 0;
int cnt[N];
// unordered_map<int, int> cnt;
struct node {
    int L, R, i;
};
node q[N];
 
bool cmp(node x, node y) {
    if (x.L / BLOCK != y.L / BLOCK) {
        // different blocks, so sort by block.
        return x.L / BLOCK < y.L / BLOCK;
    }
    // same block, so sort by R value
    return x.R < y.R;
}
 
void add(int position) {
    cnt[a[position]]++;
    if (cnt[a[position]] == 1) {
        answer++;
    }
}
 
void remove(int position) {
    cnt[a[position]]--;
    if (cnt[a[position]] == 0) {
        answer--;
    }
}
 
void solve() {
    int n, m;
    cin >> n >> m;
 
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        a[i] = v[i];
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // print(v);
 
    map<int, int> new_num;
    for (int i = 0; i < n; i++) new_num[v[i]] = i;
    // for (auto el : new_num) {
    //     cout << "lol "<< el.first << ' ' << el.second << '\n';
    // }
 
    for (int i = 0; i < n; i++) a[i] = new_num[a[i]];
    // print(a);
 
    // before this point you want your a array to contain compressed values
    // in the original order
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        q[i].L = --x;
        q[i].R = --y;
        q[i].i = i;
    }
    sort(q, q + m, cmp);
 
    int currentL = 0, currentR = 0;
    for (int i = 0; i < m; i++) {
        int L = q[i].L, R = q[i].R;
        while (currentL < L) {
            remove(currentL);
            currentL++;
        }
        while (currentL > L) {
            add(currentL - 1);
            currentL--;
        }
        while (currentR <= R) {
            add(currentR);
            currentR++;
        }
        while (currentR > R + 1) {
            remove(currentR - 1);
            currentR--;
        }
        ans[q[i].i] = answer;
    }
 
    for (int i = 0; i < m; i++)
        cout << ans[i] << '\n';
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}