# CFR 220 B. Little Elephant and Array ( Mo's Algorithm )

Problem - B - Codeforces

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1e5) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 1e9). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).

O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5;
const int MAXM = ( int ) 1e5;
const int BSZ = 400;

int N, M;
int A[ MAXN ];
int L[ MAXM ], R[ MAXM ];
int ord[ MAXM ];
int ans[ MAXM ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
for( int i = 0; i < M; ++i ){
cin >> L[ i ] >> R[ i ];
--L[ i ], --R[ i ];
ord[ i ] = i;
}
sort( ord, ord + M, [ & ]( int i, int j ){
if( L[ i ] / BSZ != L[ j ] / BSZ ) return L[ i ] / BSZ < L[ j ] / BSZ;
return R[ i ] < R[ j ];
} );
for( int f = 0, lb = 0, rb = -1; f < M; ++f ){
static unordered_map< int, int > cnt;
static int val = 0;
int i = ord[ f ];
while( L[ i ] < lb ){
--lb;
if( cnt[ A[ lb ] ] != A[ lb ] and cnt[ A[ lb ] ] + 1 == A[ lb ] ){
++val;
} else if( cnt[ A[ lb ] ] == A[ lb ] ){
--val;
}
++cnt[ A[ lb ] ];
}
while( lb < L[ i ] ){
if( cnt[ A[ lb ] ] == A[ lb ] ){
--val;
} else if( cnt[ A[ lb ] ] - 1 == A[ lb ] ){
++val;
}
--cnt[ A[ lb ] ];
++lb;
}
while( rb < R[ i ] ){
++rb;
if( cnt[ A[ rb ] ] != A[ rb ] and cnt[ A[ rb ] ] + 1 == A[ rb ] ){
++val;
} else if( cnt[ A[ rb ] ] == A[ rb ] ){
--val;
}
++cnt[ A[ rb ] ];
}
while( R[ i ] < rb ){
if( cnt[ A[ rb ] ] == A[ rb ] ){
--val;
} else if( cnt[ A[ rb ] ] - 1  == A[ rb ] ){
++val;
}
--cnt[ A[ rb ] ];
--rb;
}
ans[ i ] = val;
}
for( int i = 0; i < M; ++i ){
cout << ans[ i ] << "\n";
}
return 0;
}
```