分数: 466 分
问题陈述
有 N 书籍在高桥的书架上水平排列。最初,这本书位于 i从左边数第一个位置的耐久度为 D_i.
高桥表演 Q 按顺序对该书架进行操作。在 j第一次操作,一个整数 给出 T_j ,并执行以下程序:
- 让 M 是书架上当前剩余的图书数量。
- If T_j > M, T_j左边的第本书不存在,所以什么也没有发生。
- If T_j \leq M,该书目前的耐久度为 T_j书架上从左边算起的第一个位置减少了 1。如果耐久性变成 0,该书立即从书架上移除。被移除的书右侧的所有书都向左移动一个位置,以便其余书之间不留间隙。
每次操作结束后(包括没有任何反应的情况),输出书架上剩余的书籍数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq T_j \leq N (1 \leq j \leq Q)
- 所有输入值均为整数。
注意: T_j 最多是初始图书数 N,但可能会超出图书数量 操作时的 M 。在这种情况下,不会发生上述步骤 2 中所述的任何情况。
输入
N Q D_1 D_2 \ldots D_N T_1 T_2 \vdots T_Q
- 第一行包含两个空格分隔的整数: N,初始图书数量,以及 Q,操作次数。
- 第二行包含 N 空格分隔的整数 D_1, D_2, \ldots, D_N,其中 D_i 代表耐久性 i左起第本书。
- 以下各项 Q 行包含单个整数 T_j (1 \leq j \leq Q),表示目标位置 j-第次操作。
输出
输出 Q 行。的 j- 第行应包含书架上剩余的书籍数量 j-第次操作。
示例输入 1
5 5 1 2 3 1 2 2 4 2 1 3
示例输出 1
5 4 3 2 2
示例输入 2
3 4 1 1 1 1 1 1 1
示例输出 2
2 1 0 0
示例输入 3
10 10 2 1 3 1 2 1 4 2 1 3 3 5 1 7 2 4 3 1 2 1
示例输出 3
10 10 10 10 9 8 7 6 5 5
示例输入 4
20 25 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 1 3 5 7 2 10 15 1 3 5 8 12 1 1 2 4 6 3 2 1 5 4 3 2 1
示例输出 4
20 20 20 20 19 19 19 19 18 17 17 17 16 16 16 16 16 16 16 16 16 16 16 16 15
示例输入 5
1 1 1000000000 1
示例输出 5
1