Mo Algorithm

📌 Table of Contents

1. Introduction

For problems with queries of the form (L,R) that can be transformed between queries to find the answer, we can use the Mo Algorithm by sorting the queries as follows:


// Time complexity: (N+Q)*sqrt(N)*k 
// (k is time complexity of the add & del functions)
// value of "id" is from 1-n

struct query
{
    int l, r, id;
};
query q[maxn];

int s = sqrt(n);
bool cmp(query a,query b)
{
    if((a.l+s-1)/s!=(b.l+s-1)/s){
        return (a.l+s-1)/s<(b.l+s-1)/s;
    }
    return a.r<b.r;
}
        
When to use:

2. Sample Exercise


// Solution by Tien Minh
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const char el ='\n';
const ll maxn = 1e6+5, mod = 1e9+7;
ll n,t,s,a[maxn],mark[maxn];
ll ans[maxn],num;

struct query
{
    int l, r, id;
};
query q[maxn];

bool cmp(query a,query b)
{
    if((a.l+s-1)/s!=(b.l+s-1)/s){
        return (a.l+s-1)/s<(b.l+s-1)/s;
    }
    return a.r<b.r;
}

void add(ll x)
{
    num=num-mark[x]*mark[x]*x;
    ++mark[x];
    num=num+mark[x]*mark[x]*x;
}

void del(ll x)
{
    num=num-mark[x]*mark[x]*x;
    --mark[x];
    num=num+mark[x]*mark[x]*x;
}

void input()
{
    cin>>n>>t;
    s=sqrt(n);
    for(int i=1;i<=n;++i)   cin>>a[i];
    for(int i=1;i<=t;++i)
    {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    sort(q+1,q+t+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=t;++i)
    {
        while(r<q[i].r)
        {
            ++r;
            add(a[r]);
        }
        while(r>q[i].r)
        {
            del(a[r]);
            --r;
        }
        while(l>q[i].l)
        {
            --l;
            add(a[l]);
        }
        while(l<q[i].l)
        {
            del(a[l]);
            ++l;
        }
        ans[q[i].id]=num;
    }
    for(int i=1;i<=t;++i)   cout<<ans[i]<<el;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    return 0;
}