整数組 \((l,r)\) に課された和の条件について、 \(A_l+A_{l+1}+\dots+A_r=P-D\) と読み替えて構いません。また、 \(P-D \le 0\) の場合は \(A_i \ge 1\) という制約より条件を満たす整数組はないので、以降はそのようなケースを除去して考えます。(実装によってはこのような場合がコーナーケースになります)

条件を満たす整数組 \((l,r)\) は尺取り法により列挙できます。なお、 \(l\) を固定すると条件を満たす \(r\) は高々 \(1\) 通りであり、条件を満たす整数組は全体で高々 \(N\) 個であることに注意してください。
ここで、求めるもののうち \(C_i\) については、本問題は以下のものに帰着されます。

区間の集合 \(S\) が与えられるので、以下の形式の問いに \(Q\) 回答えよ。

• 質問として、区間 \([L_i,R_i]\) が与えられるので、 \(S\) の要素のうちこの区間の内部に完全に含まれるものの数を答えよ。

一点更新・区間和取得ができるデータ構造 \(st\) (例えば segtree を用いるとよいです) 上記の問題は以下の解法で解くことができます。

• \(r=1,2,\dots,N\) について、以下を繰り返す。
  • \(S\) 中の右端が \(r\) の要素について、 \(st\) にてその要素の左端の位置に \(1\) 加算する。
  • その後、質問のうち右端が \(r\) のものについて、 \(st\) における \(l\) 以降の部分の和を答えとする。

このようにすることで、各質問について、右端が自身の右端以下であるような \(S\) の要素のうち、左端が質問の左端以上であるものだけを全て検出することができます。

\(T_i\) についても、似た解法で解くことができます。

本解法の時間計算量は \(O((N+Q) \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;

using ll=long long;
using pl=pair<ll,ll>;

pl op(pl x,pl y){
  return {x.first+y.first,x.second+y.second};
}
pl e(){
  return {0,0};
}

int main(){
  ll N,Q,P,D;
  cin >> N >> Q >> P >> D;
  P-=D;
  vector<ll> A(N);
  for(auto &nx : A){cin >> nx;}
  vector<vector<ll>> ok(N);
  if(P>0){
    ll s=0,r=0;
    for(ll l=0;l<N;l++){
      while(r<N && s<P){s+=A[r]; r++;}
      if(s==P){
        ok[r-1].push_back(l);
      }
      s-=A[l];
    }
  }
  vector<vector<pl>> ask(N);
  for(ll i=0;i<Q;i++){
    ll L,R;
    cin >> L >> R;
    L--; R--;
    ask[R].push_back({L,i});
  }
  vector<pl> res(Q);
  segtree<pl,op,e> seg(N);
  for(ll r=0;r<N;r++){
    for(auto l : ok[r]){
      auto org=seg.get(l);
      org.first++;
      org.second+=(r-l+1);
      seg.set(l,org);
    }
    for(auto [l,id] : ask[r]){
      res[id]=seg.prod(l,N);
    }
  }
  for(auto &nx : res){cout << nx.first << " " << nx.second << "\n";}
  return 0;
}