Mo's Algorithm

const int block_size = 800;


// 0 based indexing
class MosAlgorithm {
public:
    struct Query {
        int l, r, index;
        bool operator< (Query o) const {
            return make_pair(make_pair(l/block_size, r), index) < make_pair(make_pair(o.l/block_size, o.r), o.index);
        };
    };
    int N, M; // N -> Query count, M -> Max element
    vector<Query>queries;
    vector<int>range, A;
    MosAlgorithm(vector<pair<int,int>>&_queries) {
        N = _queries.size();
        for(int i=0; i<N; ++i) {
            Query q = {_queries[i].first, _queries[i].second, i};
            queries.push_back(q);
        }
        sort(queries.begin(), queries.end());
    }
    void Hash(vector<int>a) {
        map<int,int>H;
        A = a;
        for(int i=0; i<A.size(); ++i) H[A[i]] = 0;
        int cur = 0;
        for(auto &it : H) it.second = cur++;
        for(int i=0; i<A.size(); ++i) A[i] = H[A[i]];
        M = cur;
        range.resize(M+1, 0);
    }
    vector<int>process() {
        int L = 0, R = -1, cur = 0;
        vector<int>ret(N);
        for(Query q : queries) {
            while(L > q.l) {
                if(++range[A[--L]]==1) ++cur;
            }
            while(R < q.r) {
                if(++range[A[++R]]==1) ++cur;
            }
            while(L < q.l) {
                if(--range[A[L++]]==0) --cur;
            }
            while(R > q.r) {
                if(--range[A[R--]]==0) --cur;
            }
            ret[q.index] = cur;
        }
        return ret;
    }
};