Overview

For each query \([L_i, R_i]\), find the number \(C_i\) of contiguous subarrays \((l,r)\) whose interval sum equals \(P-D\) and satisfying \(L_i \leq l \leq r \leq R_i\), as well as the total sum \(T_i\) of their lengths \(r-l+1\).

Analysis

The condition

\(D + A_l + A_{l+1} + \cdots + A_r = P\)

can be rephrased as

\(A_l + A_{l+1} + \cdots + A_r = P - D\)

Since \(A_i \geq 1\), the prefix sums are strictly increasing.

Defining the prefix sum as

\(S_i = A_1 + A_2 + \cdots + A_i\)

the sum of interval \([l,r]\) is

\(S_r - S_{l-1}\)

Therefore, the intervals we want satisfy

\(S_r = S_{l-1} + (P-D)\)

Since all \(A_i\) are positive, for a fixed \(l\) there is at most one \(r\) satisfying the condition.
Thus, by performing binary search for each \(l\), we can enumerate all intervals satisfying the condition.

---

Naively checking all subintervals for each query would be \(O(QN^2)\) in the worst case, which is too slow.

Even if we enumerate all valid intervals in advance, checking all of them for each query would be \(O(NQ)\), which is also too slow.

Instead, we enumerate all intervals \((l,r)\) satisfying the condition in advance, and efficiently process queries of the form

\(L \leq l,\ r \leq R\)

This can be handled by “adding only intervals whose right endpoint \(r\) is at most the query’s \(R\), then counting those whose left endpoint \(l\) is at least \(L\).”

To do this, we sort the intervals in ascending order of right endpoint \(r\), sort the queries in ascending order of \(R\), and manage them using a Fenwick Tree (BIT).

Algorithm

First, define the target interval sum as

\(target = P - D\)

Note that special care is needed when \(target = 0\).
In this problem, since \(A_i \geq 1\) and \(l \leq r\), the sum of any non-empty interval is always positive.
Therefore, when \(target = 0\), no interval satisfies the condition.

---

1. Enumerate intervals satisfying the condition

Prepare a prefix sum array \(S\).

For each left endpoint \(l\), binary search for \(r\) such that

\(S_r = S_{l-1} + target\)

If found, save that interval \((l,r)\).
Also save the length of that interval

\(r-l+1\)

For example, save valid intervals as

\((l,r,w)\)

where \(w = r-l+1\).

---

2. Sort intervals by right endpoint \(r\)

Sort the enumerated intervals in ascending order of right endpoint \(r\).

For a query \([L,R]\), we need intervals satisfying:

• \(r \leq R\)
• \(l \geq L\)

So we add intervals in increasing order of right endpoint \(r\).

---

3. Process queries in ascending order of \(R\)

Sort the queries in ascending order of \(R\).

Let the current query being processed be \([L,R]\).

Add all intervals with right endpoint \(r \leq R\) to the Fenwick Tree.

In the Fenwick Tree, at position corresponding to left endpoint \(l\), add:

• \(1\) to the count BIT
• \(w\) to the length-sum BIT

Then, all intervals currently in the BIT satisfy \(r \leq R\).

We then need to count those with \(l \geq L\).

This can be obtained by querying the BIT for the range sum over

\([L,N]\)

From the count BIT we get \(C_i\), and from the length-sum BIT we get \(T_i\).

---

As a concrete example, suppose the valid intervals are

\((1,2)\), \((3,3)\), \((4,5)\)

For a query \([2,4]\), we need intervals satisfying

\(2 \leq l \leq r \leq 4\)

Adding only intervals with right endpoint at most \(4\) to the BIT gives us

\((1,2)\), \((3,3)\)

Among these, the ones with left endpoint at least \(2\) are

\((3,3)\)

only, so the answer is count \(1\), total length \(1\).

Complexity

• Time complexity: \(O((N+Q)\log N)\)
• Space complexity: \(O(N+Q)\)

Binary search for each \(l\) during interval enumeration takes \(O(N\log N)\), and sorting intervals and queries plus Fenwick Tree operations take \(O((N+Q)\log N)\).

Implementation Notes

• Treat \(P-D\) as target.

• When \(target=0\), since \(A_i \geq 1\), no non-empty interval satisfies the condition.

• The prefix sum can be at most around \(2 \times 10^5 \times 10^4 = 2 \times 10^9\), but the total length in the answer can be large, so use long long.

• Prepare the following 2 Fenwick Trees:

  • A BIT to manage the count of intervals
  • A BIT to manage the total length of intervals

• Since answers must be output in the original query order, store an index idx with each query.

  Source Code

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

using ll = long long;

struct Fenwick {
    int n;
    vector<ll> bit;

    Fenwick(int n = 0) : n(n), bit(n + 1, 0) {}

    void add(int idx, ll val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    ll sum(int idx) const {
        ll res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    ll range_sum(int l, int r) const {
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }
};

struct Interval {
    int l, r;
    ll w;
};

struct Query {
    int l, r, idx;
};

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

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

    vector<ll> A(N + 1), pref(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        pref[i] = pref[i - 1] + A[i];
    }

    ll target = P - D;

    vector<Interval> intervals;

    if (target > 0) {
        for (int l = 1; l <= N; l++) {
            ll need = pref[l - 1] + target;
            auto it = lower_bound(pref.begin() + l, pref.end(), need);
            if (it != pref.end() && *it == need) {
                int r = int(it - pref.begin());
                intervals.push_back({l, r, r - l + 1});
            }
        }
    }

    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        if (a.r != b.r) return a.r < b.r;
        return a.l < b.l;
    });

    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }

    sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
        return a.r < b.r;
    });

    Fenwick bitCnt(N), bitLen(N);
    vector<ll> ansC(Q, 0), ansT(Q, 0);

    int ptr = 0;
    for (const auto& q : queries) {
        while (ptr < (int)intervals.size() && intervals[ptr].r <= q.r) {
            bitCnt.add(intervals[ptr].l, 1);
            bitLen.add(intervals[ptr].l, intervals[ptr].w);
            ptr++;
        }

        ansC[q.idx] = bitCnt.range_sum(q.l, N);
        ansT[q.idx] = bitLen.range_sum(q.l, N);
    }

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

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.