← 返回题目列表

AtCoder · awc0025_e

E. 整理书架

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

有 N 书籍在高桥的书架上水平排列。最初,这本书位于 i从左边数第一个位置的耐久度为 D_i.

高桥表演 Q 按顺序对该书架进行操作。在 j第一次操作,一个整数 给出 T_j ,并执行以下程序:

  1. 让 M 是书架上当前剩余的图书数量。
  2. If T_j > M, T_j左边的第本书不存在,所以什么也没有发生。
  3. 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