#214513. [JOISC 2016] 雇佣计划 / Employment

你是否听说过 Just Odd Inventions 公司？该公司的业务是“仅仅做一些奇妙的发明（just odd inventions）”。本文中，我们将其简称为 JOI 公司。

为了扩大业务，JOI 公司决定新招聘一批员工。

共有 名候选人，每位候选人被编号为 至 ，并被赋予一个称为“评价值”的整数。

本次招聘中，公司将录用所有评价值不低于某个阈值的候选人。随后，将新录用的员工划分为若干组。新录用员工的分组方式需满足以下条件：

• 若候选人 与候选人 （）均被录用，则他们被分入同一组，当且仅当所有编号在 范围内的候选人均被录用。

作为 JOI 公司的人事负责人，你将总共处理 个查询，以预估本次招聘中可形成的组数。第 个查询属于以下两种类型之一：

• 查询类型一：求当录用所有评价值不低于 的候选人时，可形成的组数。此类查询称为“解答查询”。
• 查询类型二：将候选人 的评价值更新为 。此类查询称为“更新查询”。

题目

当给定 个查询的信息时，请编写程序，对每个“解答查询”求出对应的组数。

从标准输入读取以下数据：

• 第 1 行包含两个整数 和 ，以空格分隔。这表示共有 名候选人，你将处理 个查询。

• 接下来的 行中，第 行（）包含一个整数 ，表示在处理查询前，候选人 的评价值为 。

• 接下来的 行中，第 行（）包含 2 个或 3 个以空格分隔的整数。令第 1 个整数为 ，则该行的内容如下：

  1. 若 ，则该行包含两个整数 和 ，以空格分隔。这表示第 个查询是一个解答查询：求当录用所有评价值不低于 的候选人时，可形成的组数。
  2. 若 ，则该行包含三个整数 、、，以空格分隔。这表示第 个查询是一个更新查询：将候选人 的评价值更新为 。

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

样例输入 1

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

样例输出 1

2
1
2

样例输入 2

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

样例输出 2

0
1
3
3
2

样例输入 3

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

样例输出 3

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 [10 分]

满足以下条件：

• 。
• 。

子任务 2 [30 分]

• 对所有 （），满足 。

子任务 3 [60 分]

无额外限制。

翻译由 Qwen3-235B 完成