题目描述

在一片静谧的杜鹃花园中，出现了 $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$ 行，每行包含一个整数，分别表示初始状态以及每次突变后，最少可能存活的生物数量。

3 1
1 1
2 2
3 3
2 2 4

1
2

提示

在突变开始前，第三只生物可以依次击败第一只和第二只生物。显然，这是一种最优的战斗方式，因此答案为 $1$。

在第一次突变之后，第二只生物的攻击力变为 $2$，防御力变为 $4$。此时，第三只生物只能击败第一只生物，最终会剩下 $2$ 只生物。可以证明这是最优结果，因此答案为 $2$。

翻译由 ChatGPT-5 完成