Mo's algorithm - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

struct query {
    int L,R,id;
    query() {
        L = R = id = 0;
    }
    query(int _L, int _R, int _id) {
        L = _L;
        R = _R;
        id = _id;
    }
};

int block;

bool cmp(query q1, query q2) {
    if (q1.L/block < q2.L/block)
        return true;
    if (q1.L/block == q2.L/block && q1.R < q2.R)
        return true;
    return false;
}

const int N = 2e5+7;
int a[N];
// nb is the answer for every query, it can be long long
int nb = 0;

void ins(int id) {

}

void del(int id) {

}

int main() {
    SaveTime
    int n,q; cin >> n >> q;
    block = n/sqrt(q)+1;
    // array a is 0 based
    for (int i = 0; i < n; i++)
        cin >> a[i];
    query qr[q];
    for (int i = 0; i < q; i++) {
        int L,R; cin >> L >> R;
        qr[i] = query(L,R,i);
    }
    sort(qr, qr+q, cmp);
    int ans[q];
    int l = 0, r = -1;
    for (int i = 0; i < q; i++) {
        auto [L,R,id] = qr[i];
        L--; R--;
        while (r < R) {
            r++;
            ins(a[r]);
        }
        while (r > R) {
            del(a[r]);
            r--;
        }
        while (l < L) {
            del(a[l]);
            l++;
        }
        while (l > L) {
            l--;
            ins(a[l]);
        }
        ans[id] = nb;
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

Resources :
https://cp-algorithms.com/data_structures/sqrt_decomposition.html
Problems :
https://vjudge.net/problem/CodeChef-IITI15