aRoTky - Online C++ Compiler & Debugging Tool

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

const int N = 100004;
int n, q, a[N], freq[N], blockSize, ans[N];
int curAns = 0;

struct Query {
    int l, r, idx;
} queryList[N];

void add(int x) {
    if (freq[a[x]] == 0) curAns++;
    freq[a[x]]++;
}

void remove_(int x) {
    freq[a[x]]--;
    if (freq[a[x]] == 0) curAns--;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    blockSize = sqrt(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) {
        cin >> queryList[i].l >> queryList[i].r;
        queryList[i].idx = i;
    }
    sort(queryList, queryList + q, [](Query x, Query y) {
        int bx = x.l / blockSize, by = y.l / blockSize;
        if (bx != by) return bx < by;
        return (bx & 1) ? x.r > y.r : x.r < y.r;
    });

    int l = 0, r = -1;
    for (int i = 0; i < q; i++) {
        int L = queryList[i].l, R = queryList[i].r;
        while (r < R) add(++r);
        while (r > R) remove_(r--);
        while (l < L) remove_(l++);
        while (l > L) add(--l);
        ans[queryList[i].idx] = curAns;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}