[ABC343] F - Second Largest Query

F - Second Largest Query

Time Limit: 2 sec / Memory Limit: 1024 MB

题面

给定长度为的序列。

按顺序处理个查询。每个查询属于以下两种类型之一：

• 类型：以1 p x的形式给出。将的值更改为。
• 类型：以2 l r的形式给出。打印中第二大值的出现次数。更确切地说，打印满足的整数的数量，使得中恰好有一个不同于的更大值。

限制条件

• 对于类型查询，。
• 对于类型查询，。
• 对于类型查询，。
• 至少存在一个类型查询。
• 所有输入值均为整数。

---

输入

输入数据格式为标准输入，具体如下：

这里，是第个查询，可以采用以下格式之一给出：

输出

设为类型查询的数量。请输出行。第行应包含对第个类型查询的响应。

---

输入样例 1

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

输出样例 1

1
0
2

初始时，。

对于第一个查询，在中第二大值为，在中出现一次，因此输出。

对于第二个查询，在中没有第二大值，因此输出。

第三个查询使。

对于第四个查询，在中第二大值为，在中出现两次，因此输出。

---

输入样例 2

1 1
1000000000
2 1 1

输出样例 2

0

---

输入样例 3

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

输出样例 3

0
1
0
2
4