概要

各クエリ \([L, R]\) について、「部分配列の和が \(P-D\) になる連続区間 \((l,r)\)（\(L \le l \le r \le R\)）」の個数 \(C\) と長さ総和 \(T\) を求める問題です。
\(A_i \ge 1\) という性質を使い、各開始位置 \(l\) に対する該当終端 \(r\) を高速に前計算し、Fenwick Tree でクエリをまとめて処理します。

考察

まず条件 [ D + \sum_{k=l}^{r} Ak = P ] は [ \sum{k=l}^{r} A_k = P-D = \text{need} ] に言い換えられます。

重要な気づき1: \(A_i \ge 1\) なので二重ポインタが使える

全要素正なので、固定した \(l\) に対して右端 \(r\) を右へ進めると区間和は単調増加します。
よって各 \(l\) について「和が need になる \(r\)」は 高々1つ です。

これにより、全 \(l\) について対応する \(r\) を二重ポインタで \(O(N)\) で求められます。

• 見つかったら to[l] = r、長さ len[l] = r-l+1
• なければ to[l] = 0

重要な気づき2: クエリ条件は「to[l] が R 以下」

クエリ \([L,R]\) で有効な開始点 \(l\) は、 - \(L \le l \le R\) - かつ to[l] <= R（終端が範囲内）

つまり「左端が区間内」かつ「対応終端が現在の \(R\) までに出現済み」のものを数えればよいです。

素朴解が遅い理由

各クエリごとに \(l,r\) を全探索すると最悪 \(O(N^2)\)、
あるいは各クエリで尺取りしても \(O(NQ)\) で、制約 (\(N=2\times10^5, Q=10^5\)) では間に合いません。

解決法

to[l]=r を「終端 \(r\) ごとのバケット」に入れておき、\(R=1..N\) を走査しながら

• その時点までに終端が確定した \(l\) を Fenwick Tree に追加
  • 個数用 BIT
  • 長さ和用 BIT
• 右端が \(R\) のクエリをまとめて処理し、l in [L,R] の和を取得

これで全クエリを高速に処理できます。

アルゴリズム

1. need = P - D を計算。

   • need <= 0 の場合、部分配列和は \(A_i\ge1\) なので常に 1 以上。条件を満たす区間は存在せず、全クエリ 0 0。

2. 二重ポインタで各 l の対応 to[l] を求める。

   • cur = sum(l..r) を管理し、cur < need の間 r を進める。
   • cur == need なら記録。
   • 次の l+1 へ進むため cur -= A[l]。

3. to[l] > 0 のものを bucket[to[l]] に l として入れる（終端別管理）。

4. クエリ \((L_i,R_i)\) を qByR[R_i] に格納（右端別オフライン処理）。

5. rr=1..N を順に処理：

   • bucket[rr] にある l を BIT に追加
     • bitCnt.add(l,1)
     • bitLen.add(l,len[l])
   • qByR[rr] の各クエリ \((L,idx)\) について
     • C = bitCnt.sum(L..rr)
     • T = bitLen.sum(L..rr)

6. 元の順に答えを出力。

計算量

• 時間計算量: \(O(N + (N+Q)\log N)\)
  （尺取り \(O(N)\)、BIT 更新最大 \(N\) 回、クエリ \(Q\) 回）
• 空間計算量: \(O(N+Q)\)

実装のポイント

• need <= 0 の早期 return を入れると安全です（この問題では必ず解なし）。

• 和や答えは大きくなるので long long を使う。

• Fenwick Tree は 1-indexed で実装し、sumRange(l,r)=prefix(r)-prefix(l-1) を使う。

• クエリは右端でまとめる「オフライン処理」にするのが肝です。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<long long> bit;
    Fenwick() : n(0) {}
    Fenwick(int n_) { init(n_); }
    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }
    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }
    long long sumPrefix(int idx) const {
        long long s = 0;
        for (; idx > 0; idx -= idx & -idx) s += bit[idx];
        return s;
    }
    long long sumRange(int l, int r) const {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    long long P, D;
    cin >> N >> Q >> P >> D;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++) cin >> L[i] >> R[i];

    long long need = P - D;

    vector<long long> ansC(Q, 0), ansT(Q, 0);

    if (need <= 0) {
        // A_i >= 1, so subarray sum is always >= 1. No solution.
        for (int i = 0; i < Q; i++) {
            cout << 0 << ' ' << 0 << '\n';
        }
        return 0;
    }

    // Two pointers to find, for each l, unique r (if exists) such that sum(l..r)=need
    vector<int> to(N + 1, 0);      // matched r for l, 0 if none
    vector<int> len(N + 1, 0);     // length if matched
    int r = 0;
    long long cur = 0;
    for (int l = 1; l <= N; l++) {
        while (r < N && cur < need) {
            r++;
            cur += A[r];
        }
        if (cur == need) {
            to[l] = r;
            len[l] = r - l + 1;
        }
        cur -= A[l];
        if (r < l) { // not really needed with positive A, but keep safe
            r = l;
            cur = 0;
        }
    }

    vector<vector<int>> bucket(N + 1);
    for (int l = 1; l <= N; l++) {
        if (to[l] > 0) bucket[to[l]].push_back(l);
    }

    vector<vector<pair<int,int>>> qByR(N + 1);
    for (int i = 0; i < Q; i++) {
        qByR[R[i]].push_back({L[i], i});
    }

    Fenwick bitCnt(N), bitLen(N);

    for (int rr = 1; rr <= N; rr++) {
        for (int l : bucket[rr]) {
            bitCnt.add(l, 1);
            bitLen.add(l, len[l]);
        }
        for (auto &qq : qByR[rr]) {
            int lq = qq.first;
            int idx = qq.second;
            ansC[idx] = bitCnt.sumRange(lq, rr);
            ansT[idx] = bitLen.sumRange(lq, rr);
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ansC[i] << ' ' << ansT[i] << '\n';
    }

    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。