Overview

This problem requires efficiently finding the number of pairs \((l, r)\) whose contiguous subsequence sum equals \(P - D\) within a specified interval \([L, R]\), as well as the total sum of days for those pairs, using offline query processing and BIT (Binary Indexed Tree).

Analysis

Key Insight

The condition \(D + A_l + A_{l+1} + \cdots + A_r = P\) can be rewritten using the prefix sum \(S[i] = A_1 + \cdots + A_i\) (with \(S[0] = 0\)) as follows:

\[S[r] - S[l-1] = P - D \quad (\text{target} = P - D)\]

Since \(A_i \geq 1\), the prefix sum \(S\) is strictly monotonically increasing. This means that for each \(l\), there is at most one \(r\) that satisfies the condition. It can be found using binary search.

Problem with the Naive Approach

If we search all \((l, r)\) pairs within the interval \([L, R]\) for each query, it takes \(O(N)\) in the worst case, resulting in a total of \(O(NQ)\) for \(Q\) queries, which causes TLE.

Solution Strategy

• Precompute all valid pairs \((l, r)\) in advance
• Sort queries offline in ascending order of \(R\) and process them using a sweep line
• Use BIT to efficiently compute the number of pairs and the total sum of days within an interval

Algorithm

1. Precomputation: For each \(l = 1, \ldots, N\), find \(r\) satisfying \(S[r] = S[l-1] + \text{target}\) using binary search. If found, register \(l\) in by_r[r].

2. Offline Query Processing: Sort queries in ascending order of \(R\).

3. Sweep Line + BIT: Advance the variable cur_r from left to right:

   • When reaching cur_r, for all \(l\) contained in by_r[cur_r]:
     • Add \(+1\) at position \(l\) in cnt_bit (managing pair count)
     • Add \(+(r - l + 1)\) at position \(l\) in sum_bit (managing days)
   • For query \([L, R]\), cnt_bit.query(L, R) gives \(C_i\), and sum_bit.query(L, R) gives \(T_i\)

Key Point: The BIT is indexed by \(l\). When cur_r has advanced up to \(q.R\), the pairs registered in the BIT are those satisfying “\(r \leq q.R\)”. By querying the range \(l \geq L\) for query \([L, R]\), we count only pairs satisfying \(L \leq l\) and \(r \leq R\) (furthermore, \(l \leq r\) is already guaranteed during precomputation).

Complexity

• Time complexity: \(O(N \log N + Q \log N)\)
  • Binary search in precomputation: \(O(N \log N)\)
  • Sweep + BIT updates: At most \(N\) valid pairs, each taking \(O(\log N)\)
  • Query answering: \(O(\log N)\) each
• Space complexity: \(O(N + Q)\)

Implementation Notes

• Since \(A_i \geq 1\), the prefix sum is strictly monotonically increasing, so for each \(l\) there is at most one \(r\) satisfying the condition. This greatly simplifies the problem.

• Even when target = P - D is \(0\), since \(A_i \geq 1\), there exists no \(l \leq r\) satisfying \(S[r] - S[l-1] = 0\), so there is no issue.

• The key is sorting queries by \(R\) and sweeping, which maintains the state where “only pairs with \(r \leq R\) exist in the BIT”.

• The BIT range query query(L, R) = query(R) - query(L-1) handles the condition \(l \geq L\).

  Source Code

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

struct BIT {
    int n;
    vector<long long> tree;
    BIT(int n) : n(n), tree(n+1, 0) {}
    void update(int i, long long val) {
        for (; i <= n; i += i & (-i)) tree[i] += val;
    }
    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & (-i)) s += tree[i];
        return s;
    }
    long long query(int l, int r) {
        return query(r) - query(l-1);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    long long P, D;
    cin >> N >> Q >> P >> D;
    
    long long target = P - D;
    
    vector<long long> S(N+1, 0);
    for (int i = 1; i <= N; i++) {
        int a; cin >> a;
        S[i] = S[i-1] + a;
    }
    
    // For each l, find r_of[l] such that S[r] - S[l-1] = target
    vector<vector<int>> by_r(N+2);
    for (int l = 1; l <= N; l++) {
        long long need = S[l-1] + target;
        if (need < S[l] || need > S[N]) continue;
        // Binary search for need in S[l..N]
        int lo = l, hi = N, found = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (S[mid] == need) { found = mid; break; }
            else if (S[mid] < need) lo = mid + 1;
            else hi = mid - 1;
        }
        if (found != -1) {
            by_r[found].push_back(l);
        }
    }
    
    // Process queries offline sorted by R
    struct Query { int L, R, idx; };
    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;
    });
    
    BIT cnt_bit(N), sum_bit(N);
    vector<long long> ans_c(Q), ans_t(Q);
    
    int cur_r = 0;
    for (auto& q : queries) {
        while (cur_r < q.R) {
            cur_r++;
            for (int l : by_r[cur_r]) {
                cnt_bit.update(l, 1);
                sum_bit.update(l, (long long)(cur_r - l + 1));
            }
        }
        ans_c[q.idx] = cnt_bit.query(q.L, q.R);
        ans_t[q.idx] = sum_bit.query(q.L, q.R);
    }
    
    for (int i = 0; i < Q; i++) {
        cout << ans_c[i] << " " << ans_t[i] << "\n";
    }
    
    return 0;
}

This editorial was generated by claude4.6opus-thinking.