概要

指定された区間 \([L, R]\) 内で、連続部分列の和が \(P - D\) に等しくなるような組 \((l, r)\) の個数とその日数の総和を、オフラインクエリ処理とBIT（Binary Indexed Tree）を用いて効率的に求める問題です。

考察

重要な気づき

条件 \(D + A_l + A_{l+1} + \cdots + A_r = P\) は、累積和 \(S[i] = A_1 + \cdots + A_i\)（\(S[0] = 0\)）を定義すると、次のように書き換えられます：

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

\(A_i \geq 1\) なので累積和 \(S\) は狭義単調増加です。これにより、各 \(l\) に対して条件を満たす \(r\) は高々1つしか存在しません。二分探索で見つけることができます。

素朴なアプローチの問題点

各クエリに対して区間 \([L, R]\) 内の全ての \((l, r)\) ペアを探索すると、最悪 \(O(N)\) かかり、\(Q\) 個のクエリに対して合計 \(O(NQ)\) となりTLEします。

解決方針

• あらかじめ全ての有効なペア \((l, r)\) を前計算する
• クエリをオフラインで \(R\) の昇順にソートし、スイープラインで処理する
• BITを用いて、区間内のペア数と日数総和を高速に求める

アルゴリズム

1. 前計算: 各 \(l = 1, \ldots, N\) に対し、\(S[r] = S[l-1] + \text{target}\) を満たす \(r\) を二分探索で求め、見つかれば by_r[r] に \(l\) を登録する。

2. クエリのオフライン処理: クエリを \(R\) の昇順にソートする。

3. スイープライン + BIT: 変数 cur_r を左から右に進めながら：

   • cur_r に到達したとき、by_r[cur_r] に含まれる全ての \(l\) について：
     • cnt_bit の位置 \(l\) に \(+1\)（ペア数の管理）
     • sum_bit の位置 \(l\) に \(+(r - l + 1)\)（日数の管理）
   • クエリ \([L, R]\) に対して、cnt_bit.query(L, R) が \(C_i\)、sum_bit.query(L, R) が \(T_i\)

ポイント: BITは \(l\) でインデックス付けされています。cur_r が \(q.R\) まで進んだ時点でBITに登録されているのは「\(r \leq q.R\) を満たすペア」です。クエリ \([L, R]\) で \(l \geq L\) の範囲を問い合わせれば、\(L \leq l\) かつ \(r \leq R\)（さらに前計算時に \(l \leq r\) は保証済み）を満たすペアだけが数えられます。

計算量

• 時間計算量: \(O(N \log N + Q \log N)\)
  • 前計算の二分探索: \(O(N \log N)\)
  • スイープ＋BIT更新: 有効ペアは最大 \(N\) 個で各 \(O(\log N)\)
  • クエリ応答: 各 \(O(\log N)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

• \(A_i \geq 1\) により累積和が狭義単調増加なので、各 \(l\) に対して条件を満たす \(r\) は高々1つ。これが問題を大幅に簡単にしている。

• target = P - D が \(0\) の場合でも、\(A_i \geq 1\) なので \(S[r] - S[l-1] = 0\) を満たす \(l \leq r\) は存在せず問題ない。

• クエリを \(R\) でソートしてスイープすることで、「\(r \leq R\) のペアのみがBITに存在する」状態を保つのが鍵。

• BITの区間クエリ query(L, R) = query(R) - query(L-1) で \(l \geq L\) の条件を処理する。

  ソースコード

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

この解説は claude4.6opus-thinking によって生成されました。