Overview

This problem asks you to find contiguous subarrays \((l, r)\) from a given sequence \(A\) whose sum equals a specific value (the target distance \(P\) minus the training camp portion \(D\)), and then for each query, count how many such subarrays are completely contained within a given range \([L_i, R_i]\) and compute the total sum of their lengths.

Analysis

1. Simplifying the Condition

First, let’s simplify the condition \(D + A_l + A_{l+1} + \cdots + A_r = P\). Let \(K = P - D\) be the remaining distance to run during training. Then the condition can be rewritten as: $\(A_l + A_{l+1} + \cdots + A_r = K\)$

Using the prefix sum \(S[i] = A_1 + A_2 + \cdots + A_i\) (with \(S[0] = 0\)), the left-hand side can be expressed as \(S[r] - S[l-1]\), so the condition becomes: $\(S[r] - S[l-1] = K \iff S[r] = S[l-1] + K\)$

2. Properties of Valid Pairs

Since the constraint gives \(A_i \geq 1\), the prefix sum \(S\) is strictly monotonically increasing (not just non-decreasing — the values always increase). This tells us the following: - For a given \(l\), there is at most one \(r\) that satisfies the condition. - As \(l\) increases, the corresponding \(r\) also necessarily increases (similar to the two-pointer technique, or by monotonicity).

3. Efficiently Answering Queries

Naively searching through all pairs for each query would take \(O(Q \times N)\) in the worst case, which is too slow. Instead, we enumerate all valid pairs \((l, r)\) in advance. Since \(A_i \geq 1\) and \(\sum A_i\) can be large, the total number of valid pairs is at most \(N\).

Let the enumerated pairs be \((l_1, r_1), (l_2, r_2), \dots, (l_m, r_m)\). For a query \((L_i, R_i)\), we need to find the count and total length \((r_k - l_k + 1)\) of indices \(k\) satisfying: - \(L_i \leq l_k\) and \(r_k \leq R_i\)

Here, the pairs are sorted in ascending order by \(l\), and also in ascending order by \(r\). Using this property, we can efficiently determine the range \([k_{start}, k_{end}]\) of valid \(k\) values via binary search.

Algorithm

1. Preprocessing: Compute Prefix Sums
   • Compute \(S[i] = A_1 + \dots + A_i\).
2. Preprocessing: Enumerate Valid Pairs
   • For each \(l \in [1, N]\), use binary search (std::lower_bound) to find \(r\) such that \(S[r] = S[l-1] + K\).
   • If found, add the pair \((l, r)\) to the lists L_pairs and R_pairs, and also compute a prefix sum of the lengths.
3. Query Processing
   • For each query \((L_i, R_i)\):
     • Binary search on L_pairs to find the smallest index \(k_{start}\) satisfying \(L_i \leq l_k\).
     • Binary search on R_pairs to find the largest index \(k_{end}\) satisfying \(r_k \leq R_i\).
     • If \(k_{start} \leq k_{end}\), the count is \(k_{end} - k_{start} + 1\), and the total length is computed in \(O(1)\) using the prefix sum.

Complexity

• Preprocessing: \(O(N \log N)\)
  • Computing the prefix sums takes \(O(N)\), and searching for \(r\) for each \(l\) takes \(O(N \log N)\).
• Query Processing: \(O(Q \log N)\)
  • Each query requires two binary searches, so each takes \(O(\log N)\).
• Overall: \(O((N + Q) \log N)\)
  • This is sufficiently fast for the constraints \(N, Q \approx 10^5\).
• Space Complexity: \(O(N)\)
  • Required for storing the prefix sums and the list of pairs.

Implementation Notes

• Handling \(K \leq 0\): If \(P - D \leq 0\), the goal is already achieved, or since \(A_i \geq 1\), adding any contiguous subarray would exceed the target. In this case, we handle it by treating it as having no valid pairs.

• Choosing the right binary search: When searching for \(L_i \leq l_k\), use lower_bound. When searching for \(r_k \leq R_i\), subtract 1 from the result of upper_bound, etc. Careful attention to boundary conditions is necessary.

• Fast I/O: Since \(Q\) can be large, in C++ it is standard practice to use ios::sync_with_stdio(false); cin.tie(nullptr); to speed up input and output.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 目標達成トレーニング (Goal Achievement Training)
 * 
 * この問題は、各クエリ (L_i, R_i) に対して、
 * L_i <= l <= r <= R_i かつ D + A_l + A_{l+1} + ... + A_r = P
 * を満たす整数組 (l, r) の個数 C_i と、その期間の日数 (r - l + 1) の総和 T_i を求めるものです。
 * 
 * 条件式を整理すると、A_l + ... + A_r = P - D となります。
 * K = P - D とおくと、累積和 S[i] = A_1 + ... + A_i を用いて、
 * S[r] - S[l-1] = K、すなわち S[r] = S[l-1] + K と表せます。
 * 
 * A_i >= 1 という制約から、累積和 S は狭義単調増加です。
 * したがって、各 l に対して条件を満たす r は高々1つしか存在しません。
 * また、l が増加すれば S[l-1] + K も増加するため、対応する r も増加します。
 * 
 * アルゴリズムの概要:
 * 1. 累積和 S を計算する。
 * 2. 全ての有効な組 (l, r) を見つけ、L_pairs, R_pairs リストに格納する。
 *    このとき、L_pairs と R_pairs は共に昇順に並ぶ。
 * 3. 各組の期間の日数 (r - l + 1) の累積和 T_prefix_sum を計算しておく。
 * 4. 各クエリ (L_i, R_i) に対して:
 *    - 二分探索を用いて、L_pairs[k] >= L_i を満たす最小のインデックス k_start を求める。
 *    - 二分探索を用いて、R_pairs[k] <= R_i を満たす最大のインデックス k_end を求める。
 *    - もし k_start <= k_end であれば、インデックス範囲 [k_start, k_end] の組が条件を満たす。
 *    - その個数は k_end - k_start + 1、日数の総和は累積和を用いて定数時間で計算できる。
 * 
 * 計算量:
 * - 前処理 (累積和・組の抽出): O(N log N)
 * - クエリ処理: O(Q log N)
 * - 全体: O((N + Q) log N)
 */

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    long long P, D;
    if (!(cin >> N >> Q >> P >> D)) return 0;

    // 累積和 S の計算 (S[0] = 0, S[i] = A[1] + ... + A[i])
    vector<long long> S(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        long long a;
        cin >> a;
        S[i] = S[i - 1] + a;
    }

    // トレーニングで走る必要がある残りの距離
    long long K = P - D;
    
    // 条件 S[r] - S[l-1] = K を満たす (l, r) のペアを格納
    vector<int> L_pairs, R_pairs;
    // 日数 (r - l + 1) の累積和
    vector<long long> T_prefix_sum;
    T_prefix_sum.push_back(0);

    // K <= 0 の場合、A_i >= 1 より条件を満たす l <= r は存在しない
    if (K > 0) {
        for (int l = 1; l <= N; ++l) {
            long long target = S[l - 1] + K;
            // S は単調増加なので二分探索で target を探す
            // r >= l なので S[l] 以降を探索範囲とする
            auto it = lower_bound(S.begin() + l, S.end(), target);
            if (it != S.end() && *it == target) {
                int r = (int)distance(S.begin(), it);
                L_pairs.push_back(l);
                R_pairs.push_back(r);
                T_prefix_sum.push_back(T_prefix_sum.back() + (long long)(r - l + 1));
            }
        }
    }

    // クエリへの回答
    for (int i = 0; i < Q; ++i) {
        int Li, Ri;
        cin >> Li >> Ri;
        
        // 条件を満たすペアが一つも存在しない場合
        if (L_pairs.empty()) {
            cout << "0 0\n";
            continue;
        }

        /**
         * クエリの条件は Li <= l かつ r <= Ri。
         * L_pairs と R_pairs は共に昇順であるため、
         * 1. L_pairs[k] >= Li を満たす最小の k (k_start)
         * 2. R_pairs[k] <= Ri を満たす最大の k (k_end)
         * を求めれば、その間の全ての k が条件を満たす。
         */
        int k_start = lower_bound(L_pairs.begin(), L_pairs.end(), Li) - L_pairs.begin();
        int k_end = upper_bound(R_pairs.begin(), R_pairs.end(), Ri) - R_pairs.begin() - 1;

        if (k_start <= k_end) {
            long long count = (long long)k_end - k_start + 1;
            long long total_len = T_prefix_sum[k_end + 1] - T_prefix_sum[k_start];
            cout << count << " " << total_len << "\n";
        } else {
            // 条件を満たすペアが範囲内に存在しない場合
            cout << "0 0\n";
        }
    }

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.