Cod sursă (job #799570)

#include <fstream>
#include <algorithm>

using namespace std;

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

const int Nmax = 200005;

struct subiect{
    int tip;
    int lungime;
    int poz_finish;
};

struct subiect_ordonat{
    int lungime, indice;
};

struct query{
    int capat_st, capat_dr;
    int valoare, indice;
};

int n, q, cate, aib[Nmax], sol[Nmax];
subiect subiecte[Nmax];
subiect_ordonat subiecte_ordonat[Nmax];
query queries[Nmax];

int lsb(int x){
    return (x & (-x));
}

void aib_update(int poz, int val){
    for(int i = poz; i <= n; i += lsb(i)){
        aib[i] += val;
    }
}

int aib_query_poz(int poz){
    int sum = 0;

    for(int i = poz; i > 0; i -= lsb(i)){
        sum += aib[i];
    }

    return sum;
}

int aib_query(int poz1, int poz2){
    return aib_query_poz(poz2) - aib_query_poz(poz1 - 1);
}

bool cmp_valoare(query a, query b){
    return a.valoare > b.valoare;
}

bool cmp_lungime(subiect_ordonat a, subiect_ordonat b){
    return a.lungime > b.lungime;
}

void citire_sir(){
    int tip;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> q;

    cate = 0;
    for(int i = 1; i <= n; i++){
        cin >> tip;

        if(tip == subiecte[cate].tip){
            subiecte[cate].lungime++;
        }
        else{
            subiecte[cate].poz_finish = i - 1;
            cate++;
            subiecte[cate].tip = tip;
            subiecte[cate].lungime = 1;
        }
    }

    subiecte[cate].poz_finish = n;
    n = cate;

    for(int i = 1; i <= n; i++){
        subiecte_ordonat[i].lungime = subiecte[i].lungime;
        subiecte_ordonat[i].indice = i;
    }
}

void citire_queries(){
    for(int i = 1; i <= q; i++){
        cin >> queries[i].capat_st >> queries[i].capat_dr >> queries[i].valoare;
        queries[i].indice = i;
    }
}

void sortari(){
    sort(subiecte_ordonat + 1, subiecte_ordonat + n + 1, cmp_lungime);
    sort(queries + 1, queries + q + 1, cmp_valoare);
}

int caut_bin(int val){
    int lft, rgt, mid, sol;

    lft = 1;
    rgt = n;
    sol = 0;
    while(lft <= rgt){
        mid = (lft + rgt) / 2;

        if(subiecte[mid].poz_finish >= val){
            sol = mid;
            rgt = mid - 1;
        }
        else{
            lft = mid + 1;
        }
    }

    return sol;
}

void calculare_solutie(){
    int p1, solutie, inceput, sfarsit;

    p1 = 1;
    for(int p2 = 1; p2 <= q; p2++){
        while(p1 <= n && subiecte_ordonat[p1].lungime >= queries[p2].valoare){
            aib_update(subiecte_ordonat[p1].indice, 1);
            p1++;
        }

        solutie = 0;
        inceput = caut_bin(queries[p2].capat_st);
        sfarsit = caut_bin(queries[p2].capat_dr);

        if(inceput == sfarsit){
            if(queries[p2].capat_dr - queries[p2].capat_st + 1 >= queries[p2].valoare){
                solutie++;
            }
        }
        else{
            if(sfarsit - inceput >= 2){
                solutie += aib_query(inceput + 1, sfarsit - 1);
            }

            if(subiecte[inceput].poz_finish - queries[p2].capat_st + 1 >= queries[p2].valoare){
                solutie++;
            }
            if(queries[p2].capat_dr - subiecte[sfarsit - 1].poz_finish >= queries[p2].valoare){
                solutie++;
            }
        }

        sol[queries[p2].indice] = solutie;
    }
}

void afisare_solutie(){
    for(int i = 1; i <= q; i++){
        cout << sol[i] << '\n';
    }
}

int main(){
    citire_sir();
    citire_queries();

    sortari();
    calculare_solutie();

    afisare_solutie();

    return 0;
}