P14397 [JOISC 2016] 雇佣计划 / Employment

你是否听说过 Just Odd Inventions 公司？该公司的业务是“仅仅做一些奇妙的发明（just odd inventions）”。本文中，我们将其简称为 JOI 公司。 为了扩大业务，JOI 公司决定新招聘一批员工。 共有 $N$ 名候选人，每位候选人被编号为 $1$ 至 $N$，并被赋予一个称为“评价值”的整数。 本次招聘中，公司将录用所有评价值不低于某个阈值的候选人。随后，将新录用的员工划分为若干组。新录用员工的分组方式需满足以下条件： - 若候选人 $a$ 与候选人 $b$（$a < b$）均被录用，则他们被分入同一组，当且仅当所有编号在 $[a, b]$ 范围内的候选人均被录用。 作为 JOI 公司的人事负责人，你将总共处理 $M$ 个查询，以预估本次招聘中可形成的组数。第 $j$ 个查询属于以下两种类型之一： - 查询类型一：求当录用所有评价值不低于 $B_j$ 的候选人时，可形成的组数。此类查询称为“解答查询”。 - 查询类型二：将候选人 $C_j$ 的评价值更新为 $D_j$。此类查询称为“更新查询”。 **题目** 当给定 $M$ 个查询的信息时，请编写程序，对每个“解答查询”求出对应的组数。

从标准输入读取以下数据： - 第 1 行包含两个整数 $N$ 和 $M$，以空格分隔。这表示共有 $N$ 名候选人，你将处理 $M$ 个查询。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $A_i$，表示在处理查询前，候选人 $i$ 的评价值为 $A_i$。 - 接下来的 $M$ 行中，第 $j$ 行（$1 \le j \le M$）包含 2 个或 3 个以空格分隔的整数。令第 1 个整数为 $T_j$，则该行的内容如下： 1. 若 $T_j = 1$，则该行包含两个整数 $T_j$ 和 $B_j$，以空格分隔。这表示第 $j$ 个查询是一个解答查询：求当录用所有评价值不低于 $B_j$ 的候选人时，可形成的组数。 2. 若 $T_j = 2$，则该行包含三个整数 $T_j$、$C_j$、$D_j$，以空格分隔。这表示第 $j$ 个查询是一个更新查询：将候选人 $C_j$ 的评价值更新为 $D_j$。

向标准输出逐行输出每个解答查询对应的组数。

### 样例 1 解释 1. 第 1 个查询是解答查询。当录用评价值不低于 5 的候选人 1、候选人 2 和候选人 4 时，将形成两个组：一个由候选人 1 和候选人 2 组成，另一个由候选人 4 组成。因此，输出 2。 2. 第 2 个查询是更新查询。将候选人 4 的评价值更新为 1。 3. 第 3 个查询是解答查询。当录用评价值不低于 5 的候选人 1 和候选人 2 时，将形成一个由候选人 1 和候选人 2 组成的组。因此，输出 1。 4. 第 4 个查询是解答查询。当录用评价值不低于 3 的候选人 1、候选人 2、候选人 3 和候选人 5 时，将形成两个组：一个由候选人 1、候选人 2 和候选人 3 组成，另一个由候选人 5 组成。因此，输出 2。 ### 数据范围 所有输入数据满足以下条件： - $1 \le N \le 200\,000$。 - $1 \le M \le 200\,000$。 - $1 \le A_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 - $1 \le T_j \le 2$（$1 \le j \le M$）。 - $1 \le B_j \le 1\,000\,000\,000$（$1 \le j \le M$）。 - $1 \le C_j \le N$（$1 \le j \le M$）。 - $1 \le D_j \le 1\,000\,000\,000$（$1 \le j \le M$）。 - 至少存在一个 $j$（$1 \le j \le M$）满足 $T_j = 1$。 ### 子任务 **子任务 1 [10 分]** 满足以下条件： - $N \le 2000$。 - $M \le 2000$。 **子任务 2 [30 分]** - 对所有 $j$（$1 \le j \le M$），满足 $T_j = 1$。 **子任务 3 [60 分]** 无额外限制。 翻译由 Qwen3-235B 完成