[toph.co] A Very Toph Problem

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : A Very Toph Problem
Source            : toph.co
Category          : Data Structure
Algorithm         : MO's Algorithm
Verdict           : Accepted

#include <bits/stdc++.h>  
   
using namespace std;  
   
static const int naxn = 1e5 + 5;  
static const int block = 320;  
   
struct mo  
{  
      int l, r, id;  
      mo(int l = 0, int r = 0, int id = 0) : l(l), r(r), id(id) {}  
      friend bool operator < (mo p, mo q)  
      {  
            int pb = p.l / block;  
            int qb = q.l / block;  
            if (pb != qb) return p.l < q.l;  
            return (p.r < q.r) ^ (p.l / block % 2);  
      }  
} queries[naxn];  
   
int arr[naxn];  
int f[naxn];  
int ff[naxn];  
   
int l = 1, r = 0, ANS[naxn];  
int maxi, mini;  
   
inline void add(int pos)  
{  
      int x = arr[pos];  
      ff[f[x]]--;  
      int pre = f[x];  
      f[x]++;  
      ff[f[x]]++;  
      int now = f[x];  
      if (now >= maxi) maxi = now;  
      if (now <= mini) mini = now;  
}  
   
inline void remov(int pos)  
{  
      int x = arr[pos];  
      ff[f[x]]--;  
      int pre = f[x];  
      f[x]--;  
      ff[f[x]]++;  
      int now = f[x];  
      if (now >= maxi) maxi = now;  
      if (now <= mini) mini = now;  
}  
   
int main()  
{  
      int n, q;  
      scanf("%d %d", &n, &q);  
      for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);  
      for (int i = 0; i < q; i++)  
      {  
            int a, b;  
            scanf("%d %d", &a, &b);  
            queries[i] = {a, b, i};  
      }  
      sort(queries, queries+q);  
      maxi = 1;  
      mini = 1234567;  
      for (int i = 0; i < q; i++)  
      {  
            int L = queries[i].l;  
            int R = queries[i].r;  
            int ID = queries[i].id;  
            while (l > L)   add(--l);  
            while (r < R)   add(++r);  
            while (l < L)   remov(l++);  
            while (r > R)   remov(r--);  
            for (int j = maxi; j >= 1; j--)  
            {  
                  if (ff[j] > 0)  
                  {  
                        maxi = j;  
                        break;  
                  }  
            }  
            for (int j = mini; j <= maxi; j++)  
            {  
                  if (ff[j] > 0)  
                  {  
                        mini = j;  
                        break;  
                  }  
            }  
            ANS[ID] = maxi - mini;  
      }  
      for (int i = 0; i < q; i++) printf("%d\n", ANS[i]);  
}