P1503 The Enemy Enters the Village

Xiao Ka is watching TV in the living room of the new home. On TV, the endlessly re-run “Drawing Sword” (Liangjian) is playing. In the show, the Independent Regiment led by Li Yunlong encounters an enemy squad in a county seat, and they begin a guerrilla war.

There are $n$ houses in the county connected by tunnels in a line. The $i$-th house is connected only to the $(i-1)$-th and $(i+1)$-th houses. Specifically, house $1$ is connected only to house $2$, and house $n$ is connected only to house $n-1$. There are $m$ messages arriving in order: 1. If the message is ```D x```: the enemy destroys house $x$, and the tunnel is blocked. 2. If the message is ```R```: the villagers repair the most recently destroyed house. 3. If the message is ```Q x```: a soldier is trapped in house $x$. Define reachability as follows: if there exist houses $i, j$ ($1 \leq i \leq j \leq n$) such that for every $k$ with $i \leq k \leq j$, house $k$ is not destroyed, then house $i$ and house $j$ are mutually reachable. Li Yunlong is nervous after receiving the information. He wants to know, for each trapped soldier, how many houses he can reach.

The first line contains two integers $n, m$. Each of the next $m$ lines contains one of the three messages described above.

For each trapped soldier, output the number of houses he can reach.

Constraints $1 \leq n, m \leq 5 \times 10^4$. If a soldier is trapped in a destroyed house, he can only wait to die. Translated by ChatGPT 5