Cod sursă (job #802767)

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("calin.in");
ofstream cout("calin.out");

vector<long long> a[200000];
long long v[200000];

void genmat(const int& n)
{
    int prv=0, x;
    cin>>prv;
    v[0]=1;
    a[v[0]].push_back(1);
    for(int i=1; i<n; i++)
    {
        cin>>x;
        if(x==prv)
            v[i]=v[i-1]+1;
        else
            v[i]++;
        a[v[i]].push_back(i+1);
        prv=x;
    }
}

void writemat()
{
    for(int i=0; i<200000; i++)
    {
        if(!a[i].empty())
        {
            for(int e: a[i])
                cout<<e<<" ";
            cout<<"\n";
        }
    }
}

void query(const int& q)
{
    int l, r, k, st, dr;
    
    for(int i=0; i<q; i++)
    {
        cin>>l>>r>>k;

        if(a[k].empty())
        {
            cout<<0<<"\n";
            continue;
        }
        
        st=upper_bound(a[k].begin(),a[k].end(), l+k-1)-a[k].begin();
        dr=upper_bound(a[k].begin(),a[k].end(), r)-a[k].begin();

        //cout<<st<<" "<<dr<<"\n";

        if(v[l+k-1]>=k)
            dr++;
        cout<<(dr-st)<<"\n";
    }
}


int main()
{
    ios::sync_with_stdio(false);

    long long n, q;
    cin>>n>>q;

    genmat(n);
    //writemat();
    query(q);

    return 0;
}