P14447 [ICPC 2025 Xi'an R] Azalea Garden

In a serene garden of azaleas, $n$ dangerous creatures have appeared. Each creature possesses an $\textit{attack power}$ and a $\textit{defense power}$. Initially, the $i$-th creature ($1 \leq i \leq n$) has an attack power of $a_i$ and a defense power of $b_i$. You, the guardian of the azalea garden, can mentally imagine a $\textit{war}$ between them. A $\textit{war}$ consists of several (possibly, $0$) $\textit{battles}$. In each imagined $\textit{battle}$, you choose two living creatures $i$ and $j$ ($1 \leq i, j \leq n$, $i \neq j$), and: - If the attack power of creature $i$ is greater than or equal to the defense power of creature $j$ (i.e. $a_i \geq b_j$), then $i$ can defeat $j$ in the battle, and $j$ is considered eliminated. - Otherwise, nothing happens. Note that the $\textit{wars}$ are imaginary; that is, a creature eliminated cannot be used for future $\textit{battles}$ in the same $\textit{war}$, but it regains its vigor at the beginning of the next $\textit{war}$, and thus can participate in future $\textit{battles}$ of consequent $\textit{wars}$. The creatures are volatile and undergo mutations over time. You are given $q$ mutations. After each of the mutations, the attributes of a creature change. Specifically, in the $i$-th mutation, the $v_i$-th creature has its attack power updated to $x_i$ and its defense power updated to $y_i$. Note that the mutations are persistent; After the $i$-th mutation, the impacts of the first $i-1$ mutations are accumulated. Since each remaining creature poses an ongoing threat to the flowers, you want to find the minimum possible number of creatures that remain after an optimal sequence of an imagined $\textit{war}$. You need to answer the question for all states before all mutations and after each mutation.

The first line of the input contains two integers $n$ and $q$ ($1 \leq n \leq 4 \cdot 10^5$, $0 \leq q \leq 4 \cdot 10^5$), where $n$ is the number of creatures and $q$ is the number of mutations. The next $n$ lines of the input describe all the creatures. The $i$-th line of these contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq 10^9$), where $a_i$ is the attack power and $b_i$ is the defense power of the $i$-th creature. The next $q$ lines of the input describe all the mutations. The $i$-th line of these contains three integers $v_i$, $x_i$, and $y_i$ ($1 \leq v_i \leq n$, $1 \leq x_i, y_i \leq 10^9$), where $x_i$ is the new attack power of creature $v_i$ and $y_i$ is the new defense power of creature $v_i$.

Output $q + 1$ lines, each containing a single integer, which are the answers before any mutations and after each mutation in sequence.

In the example, before the mutations begin, the third creature can defeat the first and second creatures. Clearly, this is the optimal sequence of imagined battles, so the answer is $1$. After the first mutation ends, the attack power of the second creature becomes $2$, and its defense power becomes $4$. Now the third creature can only defeat the first creature, leaving $2$ creatures remaining. It can be proved that no better solution exists, so the answer is $2$.