概要

この問題は、与えられた数列 \(A\) の中から、合計が特定の数（目標距離 \(P\) から合宿分 \(D\) を引いた値）になる連続部分列 \((l, r)\) を探し、さらにクエリで与えられた範囲 \([L_i, R_i]\) に完全に含まれるものの個数と長さの総和を求める問題です。

考察

1. 条件式の整理

まず、条件式 \(D + A_l + A_{l+1} + \cdots + A_r = P\) を整理します。 トレーニングで走るべき残りの距離を \(K = P - D\) とおくと、条件は以下のように書き換えられます。 $\(A_l + A_{l+1} + \cdots + A_r = K\)$

ここで、累積和 \(S[i] = A_1 + A_2 + \cdots + A_i\) （ただし \(S[0] = 0\)）を用いると、左辺は \(S[r] - S[l-1]\) と表せるため、条件は次のようになります。 $\(S[r] - S[l-1] = K \iff S[r] = S[l-1] + K\)$

2. 条件を満たすペアの性質

制約より \(A_i \geq 1\) であるため、累積和 \(S\) は広義ではなく狭義単調増加（常に値が増え続ける）です。 これにより、以下のことが分かります。 - ある \(l\) に対して、条件を満たす \(r\) は高々1つしか存在しません。 - \(l\) が大きくなれば、対応する \(r\) も必ず大きくなります（尺取り法の要領、あるいは単調性）。

3. クエリへの効率的な回答

単純に各クエリごとに全探索すると、最悪 \(O(Q \times N)\) かかり間に合いません。 そこで、あらかじめ条件を満たす全てのペア \((l, r)\) を列挙しておくことを考えます。 \(A_i \geq 1\) かつ \(\sum A_i\) が大きくなりうるため、条件を満たすペアの総数は最大でも \(N\) 個です。

列挙したペアを \((l_1, r_1), (l_2, r_2), \dots, (l_m, r_m)\) としたとき、クエリ \((L_i, R_i)\) で求めるのは、以下の条件を満たすインデックス \(k\) の個数と長さ \((r_k - l_k + 1)\) の総和です。 - \(L_i \leq l_k\) かつ \(r_k \leq R_i\)

ここで、ペアは \(l\) について昇順に並んでおり、かつ \(r\) についても昇順に並んでいるという性質を利用すると、二分探索によって条件を満たす \(k\) の範囲 \([k_{start}, k_{end}]\) を高速に特定できます。

アルゴリズム

1. 前処理：累積和の計算
   • \(S[i] = A_1 + \dots + A_i\) を計算します。
2. 前処理：有効なペアの列挙
   • 各 \(l \in [1, N]\) について、\(S[r] = S[l-1] + K\) となる \(r\) を二分探索（std::lower_bound）で探します。
   • 見つかった場合、その \((l, r)\) をリスト L_pairs, R_pairs に追加し、長さの累積和も計算しておきます。
3. クエリ処理
   • 各クエリ \((L_i, R_i)\) に対し：
     • L_pairs を二分探索し、\(L_i \leq l_k\) を満たす最小のインデックス \(k_{start}\) を見つける。
     • R_pairs を二分探索し、\(r_k \leq R_i\) を満たす最大のインデックス \(k_{end}\) を見つける。
     • \(k_{start} \leq k_{end}\) であれば、個数は \(k_{end} - k_{start} + 1\)、長さの総和は累積和を用いて \(O(1)\) で計算する。

計算量

• 前処理: \(O(N \log N)\)
  • 累積和の計算に \(O(N)\)、各 \(l\) に対する \(r\) の探索に \(O(N \log N)\) かかります。
• クエリ処理: \(O(Q \log N)\)
  • 各クエリに対して二分探索を2回行うため、1回あたり \(O(\log N)\) です。
• 全体: \(O((N + Q) \log N)\)
  • 制約 \(N, Q \approx 10^5\) に対して十分に高速です。
• 空間計算量: \(O(N)\)
  • 累積和やペアのリストを保持するために必要です。

実装のポイント

• \(K \leq 0\) の処理: \(P - D \leq 0\) の場合、目標は既に達成されているか、\(A_i \geq 1\) より連続区間を足すと目標を超えてしまいます。この場合は条件を満たすペアが存在しないとして処理します。

• 二分探索の使い分け: \(L_i \leq l_k\) を探すときは lower_bound、\(r_k \leq R_i\) を探すときは upper_bound の結果から 1 引くなど、境界条件に注意が必要です。

• 高速な入出力: \(Q\) が大きいため、C++ の場合は ios::sync_with_stdio(false); cin.tie(nullptr); を使用して入出力を高速化するのが定石です。

  ソースコード

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

---

この解説は gemini-3-flash-thinking によって生成されました。