Cod sursă (job #800080)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("calin.in");
ofstream fout("calin.out");

int const MAX=2e5+5;
int n,q;
int v[MAX];
int nr[MAX]; /// apartine nrului
int sir[MAX]; /// sirul de nr
int st[MAX],dr[MAX]; /// st si dr pt numarul i

struct AIB{
    int n;
    int v[MAX];
    int total;
    void init(int n){
        this->n=n;
        total=0;
    }
    int ub(int x){
        return x&(-x);
    }
    void add(int pos,int val){
        while(pos<=n){
            v[pos]+=val;
            pos+=ub(pos);
        }
        total+=val;
    }
    int sum(int pos){
        int s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
    void inc(int pos){
        add(pos,1);
    }
    int mare(int pos){
        return total-sum(pos-1);
    }
}aib;

struct query{
    int l,r,k;
}qry[MAX];

void read(){
    fin>>n>>q;
    int i;
    for(i=1;i<=n;++i){
        fin>>v[i];
    }
    for(i=1;i<=q;++i){
        fin>>qry[i].l>>qry[i].r>>qry[i].k;
    }
}

struct intrb{
    int k,ind,tip;
};

vector<intrb>askk[MAX];
int rasp[MAX];

void precalc(){
    int i;
    for(i=1;i<=n;++i){
        if(v[i]!=v[i-1]){
            nr[i]=nr[i-1]+1;
            st[nr[i]]=i;
            dr[nr[i]-1]=i-1;
            sir[nr[i]-1]=dr[nr[i]-1]-st[nr[i]-1]+1;
        }
        else{
            nr[i]=nr[i-1];
        }
    }
    dr[nr[n]]=n;
    sir[nr[n]]=n-st[nr[n]]+1;
    for(i=1;i<=q;++i){
        int l=qry[i].l;
        int r=qry[i].r;
        int k=qry[i].k;
        int nrr=nr[r];
        int nrl=nr[l];
        if(nrl==nrr){
            if(r-l+1>=k){
                rasp[i]=1;
            }
            else{
                rasp[i]=0;
            }
        }
        else{
        if(r-st[nrr]+1>=k)
            ++rasp[i];
        if(dr[nrl]-st[nrl]+1>=k)
            --rasp[i];
        if(dr[nrl]-l+1>=k)
            ++rasp[i];
        askk[nrl].push_back({k,i,-1});
        askk[nrr].push_back({k,i,1});
        }
    }
}

void answer(){
    aib.init(n);
    int i;
    for(i=1;i<=nr[n];++i){
        for(auto ques : askk[i]){
            int k=ques.k;
            int ind=ques.ind;
            int tip=ques.tip;
            rasp[ind]+=tip*aib.mare(k);
        }
        aib.inc(sir[i]);
    }
}

void write(){
    int i;
    for(i=1;i<=q;++i){
        fout<<rasp[i]<<'\n';
    }
}

int main()
{
    read();
    precalc();
    answer();
    write();
    return 0;
}