P2969 [USACO09DEC] Music Notes S

FJ 准备教他的奶牛们演奏一首歌曲。这首歌由 $N$ 个音符组成，其中第 $i$ 个音符持续 $B_i$ 个节拍（$1 \leq N \leq 50,000$，$1 \leq B_i \leq 10,000$），因此整首歌的长度不会超过 500,000,000 个节拍。奶牛们将在时间 0 开始演奏这首歌，因此它们将在时间 0 到时间 $B_1$ 之前演奏第 1 个音符，在时间 $B_1$ 到时间 $B_1 + B_2$ 之前演奏第 2 个音符，依此类推。 然而，最近奶牛们对这首歌失去了兴趣，因为它们觉得这首歌太长且无聊。因此，为了确保奶牛们集中注意力，他向它们提出了 $Q$ 个问题（$1 \leq Q \leq 50,000$），问题的形式为「在时间 $T$ 到时间 $T+1$ 之前的区间内，你应该演奏哪个音符？」奶牛们需要你的帮助来回答这些问题，这些问题以 $T_i$ 的形式给出（$0 \leq T_i \leq \text{end\_of\_song}$）。 考虑这首由三个音符组成的歌曲，音符的持续时间分别为 2、1 和 3 个节拍： ```cpp Beat: 0 1 2 3 4 5 6 ... |----|----|----|----|----|----|--- ... 1111111111 : : 22222: : 333333333333333: ``` 这里有一组五个查询及其对应的答案： Query Note 2 2 3 3 4 3 0 1 1 1

\* 第 1 行：两个用空格分隔的整数：$N$ 和 $Q$ \* 第 2 行到第 $N+1$ 行：第 $i+1$ 行包含一个整数：$B_i$ \* 第 $N+2$ 行到第 $N+Q+1$ 行：第 $N+i+1$ 行包含一个整数：$T_i$

\* 第 1 行到第 $Q$ 行：对于每个查询，输出一个整数，表示奶牛们应该演奏的音符的索引。

（由 ChatGPT 4o 翻译）