JOI 2018 春合宿 Worst Reporter 3(最悪の記者 3) 難易度8

頭こんがらがる
考えにくいので、最初距離1ずつあけてなくて全員地点0にいると考えると、ちょっと考えやすくなる

signed main(){
    int N,Q;cin >> N >> Q;
    vector<int>D(N+1);
    rep(i,N){
        cin >> D[i];
        D[i]-=1;
    }
    vector<int>S(N);//周期
    rep(i,N){
        if(i==0)S[i] = D[i]+1;
        else S[i] = ((D[i]+S[i-1])/S[i-1])*S[i-1];
    }
    
    auto g = [&](int t,int i)->int {
        if(i==-1)return INF;
        if(i==N)return -INF;
        //時刻tの位置
        return t/S[i]*S[i]-(i+1);
    };


    //時刻tに位置rかそれより前のものの個数
    auto f = [&](int t,int r)->int {
        //添え字が小さい方が位置が進んでいる
        if(g(t,N-1)>r){
            if(t<=r)return 1;
            return 0;}
        if(g(t,0)<=r){
            if(t<=r)return N+1;
            return N;}
        int li = -1,ri = N;
        //l:当てはまらない r:当てはまる
        while(ri-li>1){
            int mid = (li+ri)/2;
            if(g(t,mid)<=r)ri = mid;
            else li = mid;
        }
        if(t<=r)return N-ri+1;
        return N-ri;
    };

    while(Q--){
        int t,l,r;cin >> t >> l >> r;
        cout << f(t,r)-f(t,l-1) << endl;
    }
    // cout << g(1,0) << endl;
    

}