P5445 [APIO2019] Street Lamps

A self-driving taxi is driving along a street in Innopolis. There are $n+1$ stops on the street, which divide the street into $n$ road segments. Each segment has a street lamp. When the $i$-th lamp is on, it lights up the segment connecting stops $i$ and $i+1$. Otherwise, this segment is dark. For safety reasons, the taxi can only drive on lit segments. In other words, the taxi can travel from stop $a$ to stop $b$ $(a

The first line contains two integers $n$ and $q$, representing the number of street lamps and the number of time moments. The second line contains a string $s$ representing the initial states of the street lamps. $s_i=1$ means the $i$-th lamp is initially on, and $s_i=0$ means the $i$-th lamp is initially off. The next $q$ lines each describe the event at a time moment. The $i$-th of these lines describes the event that happens at time $i$: - $\text{toggle}\ i$: At this time moment, the state of the $i$-th street lamp is toggled. - $\text{query}\ a\ b$: Compute, from time $0$ up to this time moment, how many time moments satisfy that the taxi can travel from stop $a$ to stop $b$. At least one event is $\text{query}$.

For each $\text{query}$ event, output a single integer on its own line, which is the answer to that query.

For all data, $1 \leq n,q \leq 3\times 10^5$, $|s|=n$, $1 \leq i \leq n$, $1 \leq a < b \leq n+1$. The detailed additional constraints and scores for subtasks are as follows. | Subtask | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | $n$, $q \leq 100$ | 20 | | 2 | For all $\text{query}\ a\ b$ events, $a=b-1$ holds | 20 | | 3 | For all $\text{toggle}\ i$ events, the $i$-th lamp will be turned on | 20 | | 4 | All $\text{toggle}$ events happen before the first $\text{query}$ event | 20 | | 5 | No additional constraints | 20 | Translated by ChatGPT 5