关键观察

把每个“不可用座位”视作一个分隔点，连续可用段就是相邻分隔点之间的空隙。若一段长度为 $L$ ，可坐人数为 $\left\lceil \tfrac{L}{2}\right\rceil$ = $\left\lfloor \tfrac{L+1}{2}\right\rfloor$ 。

因此答案始终是所有空隙的

\sum \left\lceil \frac{L}{2}\right\rceil

P3491.第3题-禁止贴贴

1000ms

Difficulty: 6

所属公司 : 蚂蚁

算法与标签>有序集合

教室里有一排 $n$ 把椅子，从 $1$ 到 $n$ 编号，每把椅子可以容纳一个人。但是由于在教室里禁止贴贴，相邻的两把椅子上不能同时有人坐。一开始，所有的椅子都是可用的。接下来，有 $q$ 个事件会依次发生:

在第 $1$ 个事件中，给定一个椅子编号 $k$ 。如果编号为 $k$ 的椅子是可用的，则将它置为不可用;否则将它置为可用。注意,每次事件的修改都是永久的 .
你需要输出 $q$ 个整数:第 $i$ 个整数代表在第 $i$ 个事件后，教室的椅子最多能容纳多少人.

第一行包含两个整数 $n,q(1≦n≦10^9,1≦q≦2·10^5)$ ,表示椅子的数量和事件的数量。

接下来 $q$ 行，第 $i$ 行包含一个整数 $k_i(1≦k_i≦n)$ ,表示第 $i$ 个事件中的椅子编号。

输出 $q$ 行，每行包含一个整数，其中第 $i$ 行的整数代表第 $i$ 次事件后的教室椅子的最大容纳人数。

输入

输出

2
2
3

说明我们用 $1$ 表示椅子可用， $0$ 表示椅子不可用。

在第 $1$ 次事件后， $1$ 号椅子变为不可用，椅子的状态为 $01111$ .最多容纳 $2$ 个人。一个可行的方案为:第一个人坐在 $2$ 号椅子，第二个人坐在 $4$ 号椅子。
在第 $2$ 次事件后， $2$ 号椅子变为不可用，椅子的状态为 $00111$ .最多容纳 $2$ 个人。一个可行的方案为:第一个人坐在 $3$ 号椅子，第二个人坐在 $5$ 号椅子。
在第 $3$ 次事件后， $1$ 号椅子变为可用，椅子的状态为 $10111$ ，最多容纳 $3$ 个人。一个可行的方案为:第一个人坐在 $1$ 号椅子，第二个人坐在 $3$ 号椅子，第三个人坐在 $5$ 号椅子。

输入

输出

500000
499999
499999

输入

预期输出（选填）