题解 | 音符(python)

import sys
import bisect

# 获取数据
n, q = map(int, input().split())
durations = map(int, input().split())
queries = map(int, input().split())

# 计算区间长度，记录结束点（本质是前缀和）
schedule = [0] * n
prefix_sum = -1
for i, t in enumerate(durations):
    prefix_sum += t
    schedule[i] = prefix_sum

# 用二分找插入位置索引实现查询
ans = [''] * q
for i, query in enumerate(queries):
    index_q = bisect.bisect_left(schedule, query)

    ans[i] = str(index_q + 1)

print('\n'.join(ans))

不用修改的区间查询用前缀和就行，查询时用二分查找（手动实现时注意相等时左插），索引即为目标区间（需要注意是否有偏移），时间复杂度为o(qlogn)