次大值查询

题目描述

给定长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。

按给定顺序处理 $Q$ 个查询。每个查询为以下两种类型之一：

• 类型 $1$：以 1 p x 的形式给出。将 $A_p$ 的值改为 $x$。
• 类型 $2$：以 2 l r 的形式给出。输出 $(A_l, A_{l+1}, \ldots, A_r)$ 中第二大值的出现次数。更精确地说，输出满足 $l \le i \le r$，且在 $A_l, A_{l+1}, \ldots, A_r$ 中严格大于 $A_i$ 的不同值恰好有一个的整数 $i$ 的个数。

输入格式

输入按以下格式从标准输入给出：

N Q
A_1 A_2 … A_N
query_{1}
⋮
query_{Q}

这里，$\text{query}_{i}$ 是第 $i$ 个查询，格式为以下两种之一：

1 p x

2 l r

输出格式

设 $q$ 为类型 $2$ 查询的个数。输出 $q$ 行。

第 $i$ 行应输出对第 $i$ 个类型 $2$ 查询的响应。

样例

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

1
0
2

初始时，$A = (3, 3, 1, 4, 5)$。

对于第一个查询，$(3, 3, 1)$ 中第二大值为 $1$，在 $3, 3, 1$ 中出现 $1$ 次，因此输出 $1$。

对于第二个查询，$(5)$ 中不存在第二大值，因此输出 $0$。

第三个查询将 $A$ 变为 $(3, 3, 3, 4, 5)$。

对于第四个查询，$(3, 3, 4)$ 中第二大值为 $3$，在 $3, 3, 4$ 中出现 $2$ 次，因此输出 $2$。

1 1
1000000000
2 1 1

0

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

0
1
0
2
4

数据范围

• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• 对于类型 $1$ 查询，$1 \le p \le N$
• 对于类型 $1$ 查询，$1 \le x \le 10^9$
• 对于类型 $2$ 查询，$1 \le l \le r \le N$
• 至少有一个类型 $2$ 查询
• 所有输入值均为整数