关键观察

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

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

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

题目内容

在一条笔直的长街上，规划了 $n$ 个路灯安装点，从左到右依次编号为 $1$ 到 $n$ 。为了避免光线重叠造成眩光，相邻的两个安装点不能同时放置路灯。

最初所有安装点都是可用的。接下来会依次发生 $q$ 个事件，每个事件会指定一个安装点 $k$ ：如果该点当前是可用的，则将其永久标记为不可用（例如因为地下管线施工）；如果该点当前是不可用的，则将其恢复为可用。

每处理完一个事件，都需要知道此时在满足相邻约束的前提下，最多能放置多少个路灯。

已知：对于一段连续且全部可用的安装点，长度为 $L$ ，这段上最多能够放置的路灯数量为 $\lceil L/2 \rceil$ （等价于 $(L+1)//2$ ）。

约束条件