LazyMap

#include<stdio.h>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long int ll;
map<ll,vector<int> > field;

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        ll data;
        scanf("%lld",&data);
        field[data].push_back(i);
    }
    std::map<ll,vector<int> >::iterator it;it = field.begin();
    while(it != field.end()){
        sort(field[it->first].begin(),field[it->first].end());
        advance(it,1);
    }
    for(int q = 0 ; q < m ; q ++){
        int L,R;
        ll value;
        scanf("%d %d %lld",&L,&R,&value);
        it = field.find(value);
        if(it == field.end()){
            printf("0\n");
            continue;
        }

        vector<int> vec = it -> second;
        int Lidx = 0,Ridx = vec.size() - 1;
        int l =  0 , r = vec.size() - 1;
        while(l <= r){
            int m = (l+r)/2;
            if(vec[m] <= R){
                l = m + 1;
            }
            else if(vec[m] > R){
                r = m - 1;
                Ridx = min(Ridx,m);
            }
        }
        l = 0 ; r = vec.size() - 1;
        while(l <= r){
            int m = (l+r)/2;
            if(vec[m] >= L){
                r = m - 1;
            }
            else if(vec[m] < L){
                l = m + 1;
                Lidx = max(Lidx,m);
            }
        }
    /*  printf("\n%d | ",value);
        for(int i=0;i<vec.size();i++){
            printf("%d ",vec[i]);
        }
        printf("\n %d %d\n",Lidx,Ridx);*/
        if(Lidx == 0 && vec[0] >= L)Lidx--;
        if(Ridx == vec.size() - 1 && vec[vec.size()-1] <= R)Ridx++;
        printf("%d\n",Ridx - Lidx - 1);
    }
    return 0;
}