P4198 Building Reconstruction

Outside Xiao A’s building is a large construction site with $N$ buildings under construction. Every day, buildings on this site are torn down and rebuilt, over and over. He often stares out the window, counting how many buildings he can see. To simplify, we consider the events in a 2D plane. Xiao A is at point $(0, 0)$. The $i$-th building is represented by a line segment connecting $(i, 0)$ and $(i, H_i)$, where $H_i$ is the height of the $i$-th building. A building is considered visible if there exists a point on it with height greater than $0$ such that the line segment from $(0, 0)$ to that point does not intersect any of the segments of buildings $1, 2, \dots, i-1$. The construction lasts for $M$ days. Initially, all buildings have height $0$. On day $i$, the crew sets the height of the building with $x$-coordinate $X_i$ to $Y_i$ (the height may increase — construction, decrease — demolition, or remain unchanged — meaning the crew effectively did nothing that day). After the crew finishes each day, please tell how many buildings Xiao A can see.

The first line contains two positive integers $N, M$. The next $M$ lines each contain two positive integers $X_i, Y_i$.

Output $M$ lines. On the $i$-th line, output one integer denoting the number of buildings visible to Xiao A after day $i$.

For $100\%$ of the testdata, $1 \le X_i \le N$, $1 \le Y_i \le 10^9$, $1 \le N, M \le 10^5$. Translated by ChatGPT 5