题目描述

你是否听说过 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$。

输出格式

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

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

2
1
2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

0
1
3
3
2

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

2
1
0

提示

样例 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 完成