题意

有 $N$ 个应聘者，每人有一个整数“评价值”。
我们要处理 $M$ 次操作，操作分两类：

1. 查询（$T_j = 1$）：给定 $B_j$，聘用所有评价值 $\ge B_j$ 的人。被聘用的人按连续编号分组，即：如果 $a$ 和 $b$ 都被聘用，并且 $[a, b]$ 之间的所有人也被聘用，则 $a$ 和 $b$ 在同一组。问此时有多少组。
2. 修改（$T_j = 2$）：给定 $C_j, D_j$，将第 $C_j$ 个应聘者的评价值改为 $D_j$。

---

样例 1 解释

初始评价值：
$[8, 6, 3, 5, 4]$

• 第一次查询 $B=5$：聘用 $1, 2, 4$（评价值 $\ge 5$）。
  分组：$[1,2]$ 连续聘用，$[4]$ 单独一组，共 $2$ 组。
• 修改：第 $4$ 个应聘者评价值改为 $1$。
• 查询 $B=5$：聘用 $1, 2$，一组，输出 $1$。
• 查询 $B=3$：聘用 $1, 2, 3, 5$，分组：$[1,2,3]$ 一组，$[5]$ 一组，共 $2$ 组。

---

思路分析

关键观察

设我们聘用的员工集合是：所有 $A_i \ge B$ 的人。
把他们按编号从小到大排序，分组规则是：连续的一段被聘用的员工属于同一组。
所以，组数 = 聘用的员工数 - 相邻聘用员工中编号连续的对数。

更具体地：
设聘用的员工编号为 $p_1, p_2, \dots, p_k$（已排序），那么组数

$$\text{groups} = k - \#\{i \mid p_{i+1} = p_i + 1\} $$

即：组数 = 聘用人数 - 相邻聘用且编号连续的对数。

---

如何快速计算

对于给定的 $B$，我们要数出：

1. 有多少个 $i$ 满足 $A_i \ge B$（聘用人总数）。
2. 有多少对相邻的 $i$ 满足 $A_i \ge B$ 且 $A_{i+1} \ge B$（这些会减少组数，因为 $i$ 和 $i+1$ 在同一组）。

那么：

$$\text{答案} = \text{count\_ge}(B) - \text{count\_adj\_ge}(B) $$

其中 $\text{count\_ge}(B)$ 是 $A_i \ge B$ 的人数，$\text{count\_adj\_ge}(B)$ 是满足 $A_i \ge B$ 且 $A_{i+1} \ge B$ 的相邻对 $(i, i+1)$ 的数量。

---

数据结构选择

我们需要支持：

• 单点更新 $A_i$。
• 查询：给定 $B$，快速得到 $\text{count\_ge}(B)$ 和 $\text{count\_adj\_ge}(B)$。

这可以用两个 Fenwick 树（树状数组） 或 线段树 实现，按值域维护。

具体做法：

1. 对值域离散化（因为 $A_i, B_j, D_j$ 范围大，但总数 $\le 6\times 10^5$）。
2. 第一个 Fenwick 树 cnt 维护每个值有多少个 $A_i$ 等于它（用于求 $\text{count\_ge}(B)$）。
3. 第二个 Fenwick 树 adj 维护每个值有多少对相邻的 $(i, i+1)$ 的最小值 $\ge$ 该值（用于求 $\text{count\_adj\_ge}(B)$）。

---

更新操作

当修改 $A_{pos}$ 从 $old$ 变为 $new$ 时：

• 更新 cnt：在 $old$ 处 -1，在 $new$ 处 +1。
• 更新相邻关系：影响 $(pos-1, pos)$ 和 $(pos, pos+1)$ 这两对。
  • 先删除旧值对这两对的贡献（在 adj 中，在 $\min(A_{pos-1}, old)$ 处 -1，在 $\min(old, A_{pos+1})$ 处 -1）。
  • 更新 $A_{pos}$ 为 $new$。
  • 再添加新值对这两对的贡献（在 $\min(A_{pos-1}, new)$ 处 +1，在 $\min(new, A_{pos+1})$ 处 +1）。

---

查询操作

给定 $B$：

• $\text{count\_ge}(B) = \sum_{v \ge B} cnt[v]$。
• $\text{count\_adj\_ge}(B) = \sum_{v \ge B} adj[v]$。

用 Fenwick 树可以 $O(\log N)$ 求后缀和。

---

复杂度

• 离散化 $O((N+M) \log (N+M))$
• 每次操作 $O(\log N)$
• 总 $O((N+M) \log N)$

---