fsecv_0P

/// https://www.geeksforgeeks.org/array-range-queries-elements-frequency-value/
#include <bits/stdc++.h>
using namespace std;
int block;
struct Query
{
    int L,R,index;
};

bool compare(Query x, Query y)
{
    if (x.L / block != y.L / block)
        return x.L / block < y.L / block;
    return x.R < y.R;
}

void add(int x,int &currentAns,
         unordered_map<int,int>&freq)
{
    ++freq[x];
    if(freq[x]==(x+1))
        --currentAns;
    else
        if(freq[x]==x)
            ++currentAns;
}

void remove(int x,int &currentAns,unordered_map<int,int> &freq)
{
    --freq[x];
    if(freq[x]==x)
        ++currentAns;
    else
        if(freq[x]==(x-1))
            --currentAns;
}

void queryResultsUtil(int a[],Query q[],int ans[],int m)
{
    unordered_map<int,int> freq;
    int currL=0,currR=0;
    int currentAns=0;
    for(int i=0;i<m;++i)
    {
        int L=q[i].L,R=q[i].R;
        int index=q[i].index;
        while (currL < L)
        {
            remove(a[currL],currentAns,freq);
            ++currL;
        }

        while(currL>L)
        {
            --currL;
            add(a[currL],currentAns,freq);
        }
        while(currR<=R)
        {
            add(a[currR],currentAns,freq);
            ++currR;
        }
        while(currR>R+1)
        {
            --currR;
            remove(a[currR],currentAns,freq);
        }
        ans[index]=currentAns;
    }
}

void queryResults(int a[],int n,Query q[],int m)
{
    block=(int)sqrt(n);
    sort(q,q+m,compare);
    int* ans=new int[m];
    queryResultsUtil(a,q,ans,m);
    ofstream g("fsecv.out");
    for(int i=0;i<m;++i)
        g<<ans[i]<<'\n';
}

int main()
{
    int n,q,A[100000];
    ifstream f("fsecv.in");
    f>>n>>q;
    for(int i=0;i<n;++i)
        f>>A[i];
    Query queries[100000];
    for(int i=0;i<q;++i)
        f>>queries[i].L>>queries[i].R>>queries[i].index;
    queryResults(A,n,queries,q);
    return 0;
}