概要

各始点からの荷物運びの終点を前計算し、区間和クエリに高速に答える問題。

考察

この問題では、各始点 \(s\) に対して、高橋君がどこで止まるか（\(f(s)\)）を求め、さらに複数の区間 \([L_j, R_j]\) について \(f(L_j) + \cdots + f(R_j)\) を求めることになります。

愚直に各クエリごとにシミュレーションすると、最悪ケースで \(O(N)\) の計算が必要になり、全体で \(O(QN)\) となり、制約が大きいためTLEします。

そこで、各始点 \(s\) に対する \(f(s)\) を事前に計算しておけば、区間和を高速に求めることができます。

\(f(s)\) の求め方を考えます。これは「始点 \(s\) から東へ進み、累積重量が初めて \(K\) を超える地点」なので、「累積和配列上で \(acc[t] - acc[s-1] > K\) となる最小の \(t\)」を求めることと同じです。

これは、累積和配列上で二分探索を行うことで高速に求められます。

アルゴリズム

1. 入力を受け取り、累積和 \(acc[0..N]\) を計算する（\(acc[0] = 0\)）。
2. 各始点 \(s = 1, 2, ..., N\) について、\(f(s)\) を以下のように求める：
   • \(target = acc[s-1] + K\)
   • \(acc[s..N]\) の中で最初に \(target\) を超えるインデックス \(t\) を二分探索で求める。
   • そのような \(t\) が存在しなければ、\(f(s) = N\)
3. \(f[1..N]\) の累積和配列 \(f\_prefix\) を構築する。
4. 各クエリ \([L_j, R_j]\) に対して、\(f\_prefix[R_j] - f\_prefix[L_j - 1]\) を出力する。

計算量

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

実装のポイント

• 累積和を用いることで部分和を高速に計算できる。

• 二分探索を用いて各 \(f(s)\) を \(O(\log N)\) で求める。

• 区間和クエリへの応答は、累積和テーブルを用いることで \(O(1)\) で可能。

• Pythonでは bisect.bisect_right を使うと区間指定もできて便利。

  ソースコード

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    A = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # 累積和を計算
    acc = [0] + list(accumulate(A))
    
    # f(s) を前計算する
    # f(s) は最小の t >= s 使得 acc[t] - acc[s-1] > K
    # つまり acc[t] > acc[s-1] + K
    # 特别地，如果不存在这样的 t，则 f(s) = N
    
    # 使用二分查找来计算每个 f(s)
    f = [0] * (N + 1)  # f[s] 对应起点为 s 的结果（s 从1开始）
    
    import bisect
    
    # 对于每个 s (1-based), 找到最小的 t (>=s) 使得 acc[t] > acc[s-1] + K
    for s in range(1, N+1):
        target = acc[s-1] + K
        # 在 acc[s:] 中找到第一个大于 target 的索引
        # bisect_right 返回插入点，即第一个大于 target 的位置
        pos = bisect.bisect_right(acc, target, s)
        if pos > N:
            f[s] = N
        else:
            f[s] = pos
    
    # 构建 f 的前缀和以便快速回答区间和查询
    f_prefix = [0] * (N + 2)
    for i in range(1, N+1):
        f_prefix[i] = f_prefix[i-1] + f[i]
    
    results = []
    for _ in range(Q):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        res = f_prefix[R] - f_prefix[L-1]
        results.append(str(res))
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。