P14447 [ICPC 2025 Xi'an R] Azalea Garden

在一片静谧的杜鹃花园中，出现了 $n$ 只危险的生物。每只生物都拥有一个 **攻击力** 和一个 **防御力**。最初，第 $i$ 只生物（$1 \leq i \leq n$）的 **攻击力** 为 $a_i$，**防御力** 为 $b_i$。 你，作为这片杜鹃花园的守护者，可以在心中想象一场 **战争**。一场 **战争** 由若干（可能为 $0$）场 **战斗** 组成。在每一场想象中的 **战斗** 中，你选择两只仍然存活的生物 $i$ 和 $j$（$1 \leq i, j \leq n$，且 $i \neq j$），并进行如下判定： - 若生物 $i$ 的攻击力大于等于生物 $j$ 的防御力，即 $a_i \geq b_j$，则生物 $i$ 可以在本场 **战斗** 中击败生物 $j$，生物 $j$ 被视为被消灭； - 否则，不会发生任何变化。 注意，这些 **战争** 都是想象的；即在同一场 **战争** 中被消灭的生物之后不能再用于该 **战争** 的后续 **战斗**，但在下一场 **战争** 开始时，它会恢复活力，可以参与后续 **战争** 中的 **战斗**。 这些生物并不稳定，会随着时间发生突变。你会收到 $q$ 次突变操作。在第 $i$ 次突变中，第 $v_i$ 只生物的攻击力变为 $x_i$，防御力变为 $y_i$。突变是累积发生的，即第 $i$ 次突变之后，前 $i-1$ 次突变的影响依然存在。 由于每一只存活的生物都对花园构成威胁，你希望通过一场最优想象战争的战斗序列，使得最终存活的生物数量尽可能少。你需要在最初状态以及每次突变之后都回答这个最小可能存活数。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 4 \cdot 10^5$，$0 \leq q \leq 4 \cdot 10^5$），分别表示生物的数量和突变次数。 接下来 $n$ 行描述这些生物。其中第 $i$ 行包含两个整数 $a_i$ 与 $b_i$（$1 \leq a_i, b_i \leq 10^9$），分别表示第 $i$ 只生物的攻击力与防御力。 接下来 $q$ 行描述所有突变。第 $i$ 行包含三个整数 $v_i, x_i, y_i$（$1 \leq v_i \leq n$，$1 \leq x_i, y_i \leq 10^9$），表示第 $v_i$ 只生物的攻击力变为 $x_i$，防御力变为 $y_i$。

输出共 $q + 1$ 行，每行包含一个整数，分别表示初始状态以及每次突变后，最少可能存活的生物数量。

在突变开始前，第三只生物可以依次击败第一只和第二只生物。显然，这是一种最优的战斗方式，因此答案为 $1$。 在第一次突变之后，第二只生物的攻击力变为 $2$，防御力变为 $4$。此时，第三只生物只能击败第一只生物，最终会剩下 $2$ 只生物。可以证明这是最优结果，因此答案为 $2$。 翻译由 ChatGPT-5 完成