Question which include only Queries. (MO) concept

                                   http://codeforces.com/problemset/problem/221/D

                                         D. Little Elephant and Array

In this question ,we used the concept of MO , i.e. idea of rearranging the queries according to our beneficial.

Firstily , we sort the queries using this cmp function .
In all the questions in which ,the concept of MO is used "cmp" is same and  four "while loops"
 will be same. :)

we just have to change the "add" and "del"  functions for each question. :P



#include<bits/stdc++.h>

using namespace std;

long long int readInt () {
bool minus = false;
long long int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}


struct node
{
long long int lf,rt,qno;
};

long long int bck_sz,ans=0;

bool cmp(struct node a,struct node b)
{
    int  i,j;
    i=a.rt/bck_sz;
    j=b.rt/bck_sz;
    if(i==j)
    {
        if(a.lf<b.lf)
            return 1;
        else
            return 0;
    }
    else{
        if(i<j)
            return 1;
        else
            return 0;
    }
}



long long int has[1000005];

void add(long long int num)
{
if(num>1000004)
return ;
if(has[num]>num)
{
has[num]++;
}
else if(has[num]==num)
{
ans--;
has[num]++;
}
else
{
      has[num]++;
   if(has[num]==num)
   ans++;
}

}


void del(long long int num)
{

if(num>1000004)
return ;

if(has[num]>num)
{
if(has[num]>0)
has[num]--;

if(has[num]==num)
   ans++;

}
else if(has[num]==num)
{
ans--;
if(has[num]>0)
has[num]--;
}
else
{
if(has[num]>0)
      has[num]--;
}
}



int main()
{
long long int n,i,j,k,l,r,q,x,y;
n=readInt();
q=readInt();

long long int arr[n+1];
for(i=1;i<=n;i++)
arr[i]=readInt();
 
     bck_sz=sqrt(n);
 


long long int result[q];
node a[q];
for(i=0;i<q;i++)
{
l=readInt();
r=readInt();
a[i].lf=l;
a[i].rt=r;
a[i].qno=i;
}

   sort(a,a+q,cmp);

  // for(i=0;i<q;i++)
    //cout<<a[i].lf<<" "<<a[i].rt<<endl;

l=1,r=0;
for(i=0;i<q;i++)
{
    x=a[i].lf;
    y=a[i].rt;
    while(r<y)
    {

        r++;
        add(arr[r]);
    }
    while(l>x)
    {
        l--;
        add(arr[l]);
    }
    while(l<x)
    {
        del(arr[l]);
        l++;
    }
    while(r>y)
    {
        del(arr[r]);
        r--;
    }
    result[a[i].qno]=ans;
}


 for(i=0;i<q;i++)
  printf("%d\n",result[i]);

return 0;
}