221D - Little Elephant and Array - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ll long long
#define ld long double
#define L "\n"
#define F first
#define S second
#define pb push_back
 
const int N=5e5+50;

ll n,m,x,y,cnt;
ll sz;
ll ans[N],val[N];
ll freq[N];
struct qu{
    ll l,r,ind;
};
qu q[N];
 
bool cmp(qu &a,qu &b)
{
    if(a.l/sz==b.l/sz) return a.r<b.r;
    return a.l<b.l;
}
void add(ll ind)
{
    ll x=val[ind];
    if(x>n) return ;
    if(freq[x]==x) cnt--;
    freq[x]++;
    if(freq[x]==x) cnt++;
    return ;
}
void rem(ll ind)
{
    ll x=val[ind];
    if(x>n) return ;
    if(freq[x]==x) cnt--;
    freq[x]--;
    if(freq[x]==x) cnt++;
    return ;
}
int main()
{
    IOS
    ll T = 1 ;
    //cin >> T ;
    while(T--)
    {
        cin>>n>>m;
        sz=sqrt(n)+1;
        for(ll i=0 ; i<n ; i++)
        {
            cin>>val[i];
        }
        for(ll i=0 ; i<m ; i++)
        {
            cin>>q[i].l>>q[i].r;
            q[i].l--;
            q[i].r--;
            q[i].ind=i;
        }
        sort(q,q+m,cmp);
        ll l=0,r=-1;
        for(ll i=0 ; i<m ; i++)
        {
            while(r<q[i].r)
            {
                r++;
                add(r);
            }
            while(r>q[i].r)
            {
                rem(r);
                r--;
            }
            while(l<q[i].l)
            {
                rem(l);
                l++;
            }
            while(l>q[i].l)
            {
                l--;
                add(l);
            }
            ans[q[i].ind]=cnt;
        }
        for(ll i=0 ; i<m ; i++) cout<<ans[i]<<L;
    }
}