← 返回题目列表

AtCoder · abc411_c

E. 黑色间隔

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

分数: 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