Mo algorithm

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAXQ = 1000001, MAXN = 100001, MAXNUM = 100001;

struct Query
{
    int l, r, Qid, block;
    bool operator < (const Query &b) const
    {
        if(block == b.block)
            if(block & 1) return r < b.r;
            else return r > b.r;

        return block < b.block;
    }
}qry[MAXQ];

int N, Q, unit, maxcur = -1;
int arr[MAXN], app[MAXNUM] {}, cnt[MAXNUM] {};
int modeTimes[MAXQ], modeCnts[MAXQ];

void add(int x)
{
    cnt[app[x]]--;
    app[x]++;
    cnt[app[x]]++;
    maxcur = max(maxcur, app[x]);
}
void sub(int x)
{
    cnt[app[x]]--;
    app[x]--;
    cnt[app[x]]++;
    if(!cnt[maxcur]) maxcur--;
}
void solve()
{
    sort(qry + 1, qry + 1 + Q);
    cnt[0] = N;
    for(int i = 1, cL = 1, cR = 0;i <= Q; i++)
    {
        while(qry[i].r > cR)
            add(arr[++cR]);

        while(qry[i].l < cL)
            add(arr[--cL]);

        while(qry[i].r < cR)
            sub(arr[cR--]);

        while(qry[i].l > cL)
            sub(arr[cL++]);

        modeTimes[qry[i].Qid] = maxcur;
        modeCnts[qry[i].Qid] = cnt[maxcur];
    }
    for(int i = 1; i <= Q; i++) printf("%d %d\n",modeTimes[i],modeCnts[i]);
}
int main()
{
    scanf("%d %d", &N, &Q);

    unit = sqrt(N);
    for(int i = 1;i <= N && scanf("%d", &arr[i]); i++);

    for(int i = 1, L, R; i <= Q; i++)
    {
        scanf("%d %d", &L, &R);
        if(L > R) swap(L, R);
        qry[i].Qid = i;
        qry[i].l = L;
        qry[i].r = R;
        qry[i].block = L / unit;
    }
    solve();

    return 0;
}