以下の \(2\) つのステップでこの問題を解きます。

1. 各子供が最終的に持っているお菓子の数を求める
2. \(L_i\) 番目の子供から \(R_i\) 番目の子供までが持っているお菓子の数の合計を集計する

1. について、各子供 \(i=1,2,\dots,M\) が貰うお菓子の数は \(\lfloor \frac{S+M-i}{M} \rfloor\) と表現することができます。また、問題文中の方法で愚直にループを回して配っても構いません。

2. について、累積和を利用することができます。
\(A_i = A_1+A_2+\dots+A_i\) となるように予め計算しておけば、 \(l\) 番目から \(r\) 番目までの合計は \(A_r-A_{l-1}\) とすることで高速に計算できます。

全体で時間計算量 \(O(M+N)\) で本問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll M,S;
  cin >> M >> S;
  vector<ll> B(M+1,0);
  for(ll i=1;i<=M;i++){
    cin >> B[i];
    B[i]+=((S+M-i)/M);
    B[i]+=B[i-1];
  }
  ll N;
  cin >> N;
  while(N--){
    ll L,R;
    cin >> L >> R;
    cout << B[R]-B[L-1] << "\n";
  }
  return 0;
}