Overview

For each query \([L, R]\), we need to find the count \(C\) and total length \(T\) of contiguous subarrays \((l, r)\) (\(L \le l \le r \le R\)) whose sum equals \(P - D\).
Using the property that \(A_i \ge 1\), we precompute the corresponding endpoint \(r\) for each starting position \(l\) efficiently, then process queries in bulk using a Fenwick Tree.

Analysis

First, the condition [ D + \sum_{k=l}^{r} Ak = P ] can be rewritten as [ \sum{k=l}^{r} A_k = P - D = \text{need} ]

Key Observation 1: Since \(A_i \ge 1\), we can use the two-pointer technique

Since all elements are positive, for a fixed \(l\), extending the right endpoint \(r\) causes the subarray sum to monotonically increase.
Therefore, for each \(l\), there is at most one \(r\) such that the sum equals need.

This allows us to find the corresponding \(r\) for all \(l\) in \(O(N)\) using two pointers.

• If found: to[l] = r, length len[l] = r - l + 1
• If not found: to[l] = 0

Key Observation 2: The query condition is “to[l] is at most R”

For a query \([L, R]\), a valid starting point \(l\) satisfies: - \(L \le l \le R\) - and to[l] <= R (the endpoint is within range)

In other words, we need to count those where “the left endpoint is within the interval” and “the corresponding endpoint has appeared by the current \(R\).”

Why the naive approach is too slow

Brute-force searching all \(l, r\) for each query is \(O(N^2)\) in the worst case.
Even using the two-pointer technique per query results in \(O(NQ)\), which is too slow for the constraints (\(N = 2 \times 10^5, Q = 10^5\)).

Solution

Place each to[l] = r into a “bucket by endpoint \(r\)”, then sweep \(R = 1..N\):

• Add each \(l\) whose endpoint has been determined up to this point into the Fenwick Tree
  • One BIT for counts
  • One BIT for length sums
• Process all queries with right endpoint \(R\) together, retrieving the sum for l in [L, R]

This allows all queries to be processed efficiently.

Algorithm

1. Compute need = P - D.

   • If need <= 0, since \(A_i \ge 1\), any subarray sum is at least 1. No interval can satisfy the condition, so output 0 0 for all queries.

2. Use two pointers to find the corresponding to[l] for each l.

   • Maintain cur = sum(l..r), advancing r while cur < need.
   • If cur == need, record the result.
   • To move to the next l + 1, subtract cur -= A[l].

3. For each to[l] > 0, insert l into bucket[to[l]] (organized by endpoint).

4. Store each query \((L_i, R_i)\) in qByR[R_i] (offline processing grouped by right endpoint).

5. Process rr = 1..N in order:

   • For each l in bucket[rr], add it to the BIT:
     • bitCnt.add(l, 1)
     • bitLen.add(l, len[l])
   • For each query \((L, idx)\) in qByR[rr]:
     • C = bitCnt.sum(L..rr)
     • T = bitLen.sum(L..rr)

6. Output the answers in the original query order.

Complexity

• Time complexity: \(O(N + (N + Q) \log N)\)
  (Two pointers \(O(N)\), BIT updates at most \(N\) times, \(Q\) queries)
• Space complexity: \(O(N + Q)\)

Implementation Notes

• Adding an early return for need <= 0 is safe (in this problem, there are guaranteed to be no solutions in that case).

• Sums and answers can become large, so use long long.

• Implement the Fenwick Tree as 1-indexed, using sumRange(l, r) = prefix(r) - prefix(l - 1).

• The key technique is “offline processing” where queries are grouped by their right endpoint.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.3-codex.