分数: 350 点
问题陈述
有 N 方块从左到右排成一排。 最初,所有方块都漆成白色。
流程 Q 按顺序查询。的 i-th 查询给出一个整数 A_i 之间 1 和 N,包含在内,并执行以下操作:
翻转颜色 A_i从左边算起第一个方格。 具体来说,如果 A_i左边第一个格子涂成白色,涂成黑色;如果它被漆成黑色,则将其漆成白色。
然后,找到连续绘制的黑色方块的间隔数。这里,连续绘制的黑色方块的间隔是一对整数 (l,r) (1\leq l\leq r\leq N) 满足以下所有条件:
- 的 l-th, (l+1)-th, \ldots, r从左边算起第几个方块全部漆成黑色。
- 要么 l=1,或 (l-1)左边第一个方块被漆成白色。
- 要么 r=N,或 (r+1)左边第一个方块被漆成白色。
约束
- 1\leq N,Q\leq 5\times 10^5
- 1\leq A_i\leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 \ldots A_Q
输出
输出 Q 行。上 i第行 (1\leq i\leq Q),输出答案 i第一个查询。
示例输入 1
5 7 2 3 3 5 1 5 2
示例输出 1
1 1 1 2 2 1 1
下面, i从左边算起第一个方格称为方格 i.
每次查询后状态如下:
- 之后 1st查询,仅限方形 2 被漆成黑色。有 1 连续绘制的黑色方块的间隔: (l,r)=(2,2).
- 之后 2nd 查询,方块 2,3 被漆成黑色。有 1 连续绘制的黑色方块的间隔: (l,r)=(2,3).
- 之后 3rd查询,仅限正方形 2 被漆成黑色。有 1 连续绘制的黑色方块的间隔: (l,r)=(2,2).
- 之后 4第查询,方块 2,5 被漆成黑色。有 2 连续绘制的黑色方块的间隔: (l,r)=(2,2), (5,5).
- 之后 5第查询,方块 1,2,5 被漆成黑色。有 2 连续绘制的黑色方块的间隔: (l,r)=(1,2), (5,5).
- 之后 6第查询,仅正方形 1,2 被漆成黑色。有 1 连续绘制的黑色方块的间隔: (l,r)=(1,2).
- 之后 7第次查询,仅正方形 1 被漆成黑色。有 1 连续绘制的黑色方块的间隔: (l,r)=(1,1).
因此,输出 1,1,1,2,2,1,1 用换行符分隔。
示例输入 2
1 2 1 1
示例输出 2
1 0
之后 2nd查询,所有方块都涂成白色,所以输出 0 上 2第一行。
示例输入 3
3 3 1 3 2
示例输出 3
1 2 1