FREQ2 - Most Frequent Value- Using Mo's Algorithm

You are given a sequence of n integers a0, a1, ..., an-1. You are also given several queries consisting of indices i and j (0 ≤ i ≤ j ≤ n-1). For each query, determine the number of occurrences of the most frequent value among the integers ai, ..., aj.

Mo's Algorithm Related Problem:

1) DQUERY - D-query , 2) FREQ2 - Most Frequent Value , 3) D. Cut and Stick  , 4) D. Powerful array , 5) Chef and Graph Queries 6) D. Tree and Queries 7) Sherlock and Inversions

   

 

///...................SUBHASHIS MOLLICK...................///

///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///

///.............ISLAMIC UNIVERSITY,BANGLADESH.............///

///....................SESSION-(14-15)....................///

#include<bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")

#pragma GCC optimization ("O3")

#pragma GCC optimization ("unroll-loops")

#define sf(a) scanf("%d",&a)

#define sf2(a,b) scanf("%d %d",&a,&b)

#define sf3(a,b,c) scanf("%d %d %d",&a,&b,&c)

#define pf(a) printf("%d",a)

#define pf2(a,b) printf("%d %d",a,b)

#define pf3(a,b,c) printf("%d %d %d",a,b,c)

#define sfl(a) scanf("%lld",&a)

#define sfl2(a,b) scanf("%lld %lld",&a,&b)

#define sfl3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)

#define pfl(a) printf("%lld",a)

#define pfl2(a,b) printf("%lld %lld",a,b)

#define pfl3(a,b,c) printf("%lld %lld %lld",a,b,c)

#define nl printf("\n")

#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long

#define pb push_back

#define MPI map<int,int>mp;

#define fr(i,n) for(i=0;i<n;i++)

#define fr1(i,n) for(i=1;i<=n;i++)

#define frl(i,a,b) for(i=a;i<=b;i++)

#define tz 100005

#define clr0(a) memset(a,0,sizeof(a))

#define clr1(a) memset(a,-1,sizeof(a))

#define space " "

#define yesp cout<<"YES"<<endl;

#define nop cout<<"NO"<<endl;

/*primes in range 1 - n

1 - 100(1e2) -> 25 pimes

1 - 1000(1e3) -> 168 primes

1 - 10000(1e4) -> 1229 primes

1 - 100000(1e5) -> 9592 primes

1 - 1000000(1e6) -> 78498 primes

1 - 10000000(1e7) -> 664579 primes

large primes ->

104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697

*/

//freopen("Input.txt","r",stdin);

//freopen("Output.txt","w",stdout);

//const int fx[]={+1,-1,+0,+0};

//const int fy[]={+0,+0,+1,-1};

//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move

//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move

//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

#define flagone(f) cout<<(f?"YES":"NO")<<endl;

#define flagzero(f) cout<<(f?"NO":"YES")<<endl;

int ar[tz],cnt[tz],ans[tz],freq[tz];

struct node

{

    int lft,right,index;

};

int mx=0;

node query[tz];

int blockSize=317;

bool cmp(node fst,node scnd)

{

    if(fst.lft/blockSize == scnd.lft/blockSize)

    {

        return fst.right/blockSize < scnd.right/blockSize;

    }

    return fst.lft<scnd.lft;

}

void addValue(int pos)

{

    cnt[ar[pos]]++;

    freq[cnt[ar[pos]]]++;

    mx=max(mx,cnt[ar[pos]]);

}

void removeValue(int pos)

{

    freq[cnt[ar[pos]]]--;

    if(freq[cnt[ar[pos]]]==0)

        mx--;

    cnt[ar[pos]]--;

}

main()

{

    timesave;

    //freopen("Input.txt","r",stdin);

    //freopen("Output.txt","w",stdout);

    int n,q,a,b;

    sf2(n,q);

    for(int i=0; i<n; i++)

    {

        sf(ar[i]);

    }

    for(int i=0; i<q; i++)

    {

        sf2(a,b);

        query[i].lft=a;

        query[i].right=b;

        query[i].index=i;

    }

    sort(query,query+q,cmp);

    int leftPointer = 0,rightPointer=0;

    for(int i=0; i<q; i++)

    {

        int leftValue = query[i].lft;

        int rightValue = query[i].right;

        int queryIndex = query[i].index;

        while(leftPointer<leftValue)

        {

            removeValue(leftPointer);

            leftPointer++;

        }

        while(leftPointer>leftValue)

        {

            addValue(leftPointer-1);

            leftPointer--;

        }

        while(rightPointer<=rightValue)

        {

            addValue(rightPointer);

            rightPointer++;

        }

        while(rightPointer>rightValue+1)

        {

            removeValue(rightPointer-1);

            rightPointer--;

        }

        ans[query[i].index]=mx;

        //cout<<leftValue<<" "<<rightValue<<" "<<mx<<endl;

    }

    for(int i=0; i<q; i++)

    {

        printf("%d\n",ans[i]);

    }

}