AT_abc343_f [ABC343F] Second Largest Query

给定一个长度为 $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)$ 中第 $2$ 大值的**个数**。更严格地说，输出满足 $l \leq i \leq r$，且在 $A_l, A_{l+1}, \ldots, A_r$ 中，恰好有 $1$ 种比 $A_i$ 大的值的整数 $i$ 的个数。

输入按以下格式从标准输入读入。 > $N$ $Q$ $A_1$ $A_2$ $\ldots$ $A_N$ $\text{query}_{1}$ > $\vdots$ > $\text{query}_{Q}$ 其中，$\text{query}_i$ 表示第 $i$ 个查询，格式如下之一： > $1$ $p$ $x$ > $2$ $l$ $r$

设类型 $2$ 的查询有 $q$ 个，请输出 $q$ 行。第 $i$ 行输出第 $i$ 个类型 $2$ 查询的答案。

### 限制条件 - $1 \leq N, Q \leq 2 \times 10^5$ - $1 \leq A_i \leq 10^9$ - 对于类型 $1$ 查询，$1 \leq p \leq N$ - 对于类型 $1$ 查询，$1 \leq x \leq 10^9$ - 对于类型 $2$ 查询，$1 \leq l \leq r \leq N$ - 至少存在一个类型 $2$ 查询 - 输入的所有值均为整数 ### 样例解释 1 初始时，$A = (3, 3, 1, 4, 5)$。第 $1$ 个查询中，区间 $(3, 3, 1)$ 的第 $2$ 大值为 $1$，在 $3, 3, 1$ 中 $1$ 出现了 $1$ 次，因此输出 $1$。第 $2$ 个查询中，区间 $(5)$ 没有第 $2$ 大值，输出 $0$。第 $3$ 个查询后，$A = (3, 3, 3, 4, 5)$。第 $4$ 个查询中，区间 $(3, 3, 4)$ 的第 $2$ 大值为 $3$，在 $3, 3, 4$ 中 $3$ 出现了 $2$ 次，因此输出 $2$。 由 ChatGPT 4.1 翻译