概要

各クエリ \([L_i, R_i]\) について、区間内に完全に含まれる連続部分列のうち、走行距離の合計が \(P-D\) になるものの個数と、その長さの合計を求めます。

考察

条件

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

は、次のように言い換えられます。

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

ここで、\(target = P - D\) とします。

---

素朴な方法では間に合わない

各クエリごとに \([L_i, R_i]\) 内のすべての区間を調べると、最悪で \(O(QN^2)\) になり間に合いません。

また、\(A_i\) はすべて正なので尺取り法を使えば、1 クエリあたり \(O(N)\) 程度にはできますが、それでも最大で

\(NQ = 2 \times 10^5 \times 10^5\)

となり、やはり間に合いません。

---

重要な気づき

\(A_i\) はすべて正の整数です。

そのため、ある左端 \(l\) を固定したとき、和が \(target\) になる右端 \(r\) は高々 1 つしかありません。

したがって、全体で条件を満たす区間の個数は高々 \(N\) 個です。

まず、配列全体から

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

を満たす区間 \((l, r)\) をすべて列挙しておきます。

その後、各クエリ \([L, R]\) に対して、

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

を満たす列挙済み区間を数えればよいです。

---

区間をどう数えるか

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

• 右端 \(r \leq R\)
• 左端 \(l \geq L\)

を満たす有効区間です。

そこで、クエリを \(R\) の昇順に処理します。

現在のクエリの \(R\) 以下の右端を持つ有効区間だけを Fenwick Tree に追加しておきます。

Fenwick Tree には、有効区間の左端 \(l\) の位置に情報を追加します。

すると、現在追加済みの区間はすべて \(r \leq R\) を満たしています。

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

全体数 \(-\) 左端が \(L-1\) 以下の数

で求められます。

長さの合計についても同様に、Fenwick Tree に区間の長さ \(r-l+1\) を加算しておけば求められます。

アルゴリズム

1. 目標値を計算する

\(target = P - D\) とします。

もし \(target = 0\) の場合、\(A_i \geq 1\) かつ区間は空でないため、和が \(0\) になる区間は存在しません。

したがって、すべてのクエリの答えは 0 0 です。

---

2. 尺取り法で有効区間を列挙する

\(A_i\) は正なので、尺取り法で全体を一度走査します。

左端 \(l\) を \(1\) から \(N\) まで動かしながら、右端 \(r\) を進めて区間和を管理します。

区間和が \(target\) になったら、その区間 \((l, r)\) を記録します。

記録する情報は以下です。

• 右端 \(r\)
• 左端 \(l\)
• 長さ \(r-l+1\)

コードでは segs に

(r, l, r - l + 1)

として保存しています。

尺取り法では右端 \(r\) は単調に増加するため、segs も右端 \(r\) の昇順に並びます。

---

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

各クエリを

(R, L, idx)

の形で保存し、\(R\) の昇順にソートします。

idx は元のクエリ順に答えを戻すための番号です。

---

4. Fenwick Tree で左端を管理する

Fenwick Tree を 2 本用意します。

• bit_c: 区間の個数を管理
• bit_t: 区間の長さの合計を管理

クエリを \(R\) の小さい順に見ていきます。

現在のクエリの \(R\) に対して、まだ追加していない有効区間のうち、右端 \(r \leq R\) のものを Fenwick Tree に追加します。

区間 \((l, r)\) を追加するときは、

• bit_c[l] に \(1\) を加算
• bit_t[l] に \(r-l+1\) を加算

します。

また、追加済み区間全体の個数 total_c と、長さ合計 total_t も管理します。

---

5. クエリに答える

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

クエリ \([L, R]\) に対して必要なのは、その中で \(l \geq L\) のものです。

Fenwick Tree では prefix sum、つまり \(1\) からある位置までの和が求められます。

そのため、

左端が L 以上の個数
= 追加済み全体の個数 - 左端が L-1 以下の個数

として求めます。

長さの合計も同様です。

答えの個数 = total_c - bit_c.sum(L - 1)
答えの長さ合計 = total_t - bit_t.sum(L - 1)

これで、各クエリを \(O(\log N)\) で処理できます。

計算量

• 時間計算量: \(O((N + Q)\log N)\)
  • 尺取り法による有効区間列挙: \(O(N)\)
  • クエリのソート: \(O(Q\log Q)\)
  • Fenwick Tree への追加・検索: \(O((N+Q)\log N)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

• \(target = 0\) の場合は、すべての \(A_i\) が正なので答えは必ず 0 0 です。

• 有効区間は高々 \(N\) 個です。これは \(A_i\) がすべて正で、左端ごとに条件を満たす右端が高々 1 つだからです。

• Fenwick Tree は 1-indexed で実装すると扱いやすいです。

• 答えはクエリをソートして処理するため、元の順番に戻すための idx を持っておく必要があります。

• 長さの合計は最大で大きくなるため、他の言語では long long などの 64 bit 整数を使う必要があります。Python では整数が任意精度なので問題ありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, Q, P, D = data[0], data[1], data[2], data[3]
    A = [0] + data[4:4 + N]
    pos = 4 + N

    target = P - D

    if target == 0:
        sys.stdout.write(("0 0\n") * Q)
        return

    queries = []
    for idx in range(Q):
        L = data[pos]
        R = data[pos + 1]
        pos += 2
        queries.append((R, L, idx))

    segs = []
    r = 0
    cur = 0

    for l in range(1, N + 1):
        while r < N and cur < target:
            r += 1
            cur += A[r]
        if cur == target:
            segs.append((r, l, r - l + 1))
        cur -= A[l]

    queries.sort()

    bit_c = [0] * (N + 2)
    bit_t = [0] * (N + 2)

    ans_c = [0] * Q
    ans_t = [0] * Q

    p = 0
    total_c = 0
    total_t = 0
    m = len(segs)

    for R, L, idx in queries:
        while p < m and segs[p][0] <= R:
            _, l, length = segs[p]
            i = l
            while i <= N:
                bit_c[i] += 1
                bit_t[i] += length
                i += i & -i
            total_c += 1
            total_t += length
            p += 1

        i = L - 1
        pref_c = 0
        pref_t = 0
        while i > 0:
            pref_c += bit_c[i]
            pref_t += bit_t[i]
            i -= i & -i

        ans_c[idx] = total_c - pref_c
        ans_t[idx] = total_t - pref_t

    out = [f"{ans_c[i]} {ans_t[i]}" for i in range(Q)]
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

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