MO's Algorithm (Distinct Elements in a Range)

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

const int maxN = 1e6 + 100;
const int block = 560;
pair<pair<int,int>,int> query[maxN]; // l,r,and query index;
int input[maxN],res[maxN],freq[maxN];

int ans = 0;

void add (int pos) {
    ++freq[input[pos]];
    if (freq[input[pos]] == 1) ++ans;
}

void remove (int pos) {
    --freq[input[pos]];
    if (freq[input[pos]] == 0) --ans;
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,q;
         cin >> n;
         for (int i = 0; i < n; ++i) cin >> input[i];
         cin >> q;
         for (int i = 0; i < q; ++i) {
             cin >> query[i].first.first >> query[i].first.second;
             query[i].second = i;
             --query[i].first.first,--query[i].first.second;
         }
         sort (query,query + q,[&](pair<pair<int,int>,int> a,pair<pair<int,int>,int> b) {
             if (a.first.first / block != b.first.first / block) {
                 return a.first.first / block < b.first.first / block;
             }
             return a.first.second < b.first.second;
         });
         int l = 0,r = -1;
         for (int i = 0; i < q; ++i) {
             while (l > query[i].first.first) --l,add(l);
             while (r < query[i].first.second) ++r,add(r);
             while (l < query[i].first.first) remove(l),++l;
             while (r > query[i].first.second) remove(r),--r;
             res[query[i].second] = ans;
         }
         for (int i = 0; i < q; ++i) cout << res[i] << '\n';
     }
     //~ cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}