概要

各クエリ \([L_i, R_i]\) について、区間和が \(P-D\) になる連続部分列 \((l,r)\) のうち、\(L_i \leq l \leq r \leq R_i\) を満たすものの個数 \(C_i\) と、長さ \(r-l+1\) の総和 \(T_i\) を求めます。

考察

条件

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

は、言い換えると

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

です。

ここで \(A_i \geq 1\) なので、累積和は単調増加します。

累積和を

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

とすると、区間 \([l,r]\) の和は

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

です。

したがって、求めたい区間は

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

を満たすものです。

\(A_i\) がすべて正なので、固定した \(l\) に対して条件を満たす \(r\) は高々 \(1\) つです。
そのため、各 \(l\) について二分探索を行えば、条件を満たす区間をすべて列挙できます。

---

素朴に各クエリごとにすべての部分区間を調べると、最悪で \(O(QN^2)\) となり間に合いません。

また、あらかじめ条件を満たす区間を列挙できたとしても、各クエリごとにそれらをすべて調べると \(O(NQ)\) になり、これも間に合いません。

そこで、条件を満たす区間 \((l,r)\) を先にすべて列挙し、クエリ

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

を高速に処理します。

これは「右端 \(r\) がクエリの \(R\) 以下の区間だけを追加しておき、左端 \(l\) が \(L\) 以上のものを数える」という形で処理できます。

そのために、区間を右端 \(r\) の昇順にソートし、クエリも \(R\) の昇順にソートして、Fenwick Tree（BIT）で管理します。

アルゴリズム

まず、目標となる区間和を

\(target = P - D\)

とします。

ただし、\(target = 0\) の場合は注意が必要です。
この問題では \(A_i \geq 1\) かつ \(l \leq r\) なので、空でない区間の和は必ず正です。
したがって、\(target = 0\) のとき条件を満たす区間は存在しません。

---

1. 条件を満たす区間を列挙する

累積和配列 \(S\) を用意します。

各左端 \(l\) について、

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

となる \(r\) を二分探索します。

見つかった場合、その区間 \((l,r)\) を保存します。
また、その区間の長さ

\(r-l+1\)

も保存しておきます。

例えば、条件を満たす区間を

\((l,r,w)\)

として保存します。ここで \(w = r-l+1\) です。

---

2. 区間を右端 \(r\) でソートする

列挙した区間を、右端 \(r\) の昇順に並べます。

クエリ \([L,R]\) に対して必要なのは、

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

を満たす区間です。

そこで、右端 \(r\) が小さい順に区間を追加していきます。

---

3. クエリも \(R\) の昇順に処理する

クエリも \(R\) の昇順にソートします。

現在処理しているクエリを \([L,R]\) とします。

右端 \(r \leq R\) である区間をすべて Fenwick Tree に追加します。

Fenwick Tree には、左端 \(l\) の位置に対して以下を追加します。

• 個数用 BIT に \(1\)
• 長さ合計用 BIT に \(w\)

すると、現在 BIT に入っている区間はすべて \(r \leq R\) を満たしています。

あとは、その中から \(l \geq L\) のものを数えればよいです。

これは BIT の区間和で

\([L,N]\)

を取得すれば求められます。

個数用 BIT から \(C_i\)、長さ合計用 BIT から \(T_i\) が得られます。

---

具体例として、条件を満たす区間が

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

だったとします。

クエリが \([2,4]\) の場合、必要なのは

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

を満たす区間です。

右端が \(4\) 以下の区間だけを BIT に入れると、

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

が入ります。

そのうち左端が \(2\) 以上なのは

\((3,3)\)

だけなので、答えは個数 \(1\)、長さ合計 \(1\) になります。

計算量

• 時間計算量: \(O((N+Q)\log N)\)
• 空間計算量: \(O(N+Q)\)

区間列挙で各 \(l\) について二分探索を行うため \(O(N\log N)\)、区間とクエリのソートおよび Fenwick Tree の操作で \(O((N+Q)\log N)\) です。

実装のポイント

• \(P-D\) を target として扱います。

• \(target=0\) の場合、\(A_i \geq 1\) なので条件を満たす非空区間は存在しません。

• 累積和は最大で \(2 \times 10^5 \times 10^4 = 2 \times 10^9\) 程度ですが、答えの長さ合計は大きくなる可能性があるため、long long を使います。

• Fenwick Tree は以下の 2 本を用意します。

  • 区間の個数を管理する BIT
  • 区間の長さ合計を管理する BIT

• クエリは元の順番で答えを出力する必要があるため、クエリに添字 idx を持たせておきます。

  ソースコード

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

---

この解説は gpt-5.5-xhigh によって生成されました。