SPOJ Most Frequent Value _FREQ2 / Sqrt Decomposition

/***
 created: 2022-07-20-02.10.30
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll int
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

struct queris
{
    ll left,right,in;

}queri[100005];

ll block=500,mx=0;

ll a[100005],f[100005],fc[100005],ans[100005];

bool cmp(queris A, queris B)
{
  if (A.left / block != B.left / block ) return A.left < B.left;
  return (A.right < B.right)^(A.left/block%2);
}

void add(ll ind)
{
    fc[f[a[ind]]]--;
    f[a[ind]]++;
    fc[f[a[ind]]]++;
    if(fc[mx+1]>0) mx++;
}

void del(ll ind)
{
    fc[f[a[ind]]]--;
    f[a[ind]]--;
    fc[f[a[ind]]]++;
    if(fc[mx]==0) mx--;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n,m,i,j,q,k,l,r;

    cin>>n>>q;

    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }

    for(i=0;i<q;i++)
    {
        cin>>queri[i].left>>queri[i].right;
        queri[i].in=i;
    }

    sort(queri,queri+q,cmp);

    l=0,r=-1;

    for(i=0;i<q;i++)
    {
        ll cl=queri[i].left;
        ll cr=queri[i].right;
        ll ci=queri[i].in;

        while(r<cr) add(++r);
        while(l>cl) add(--l);
        while(r>cr) del(r--);
        while(l<cl) del(l++);

        ans[ci]=mx;
    }

    for(i=0;i<q;i++) cout<<ans[i]<<nl;

    get_lost_idiot;
}