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

输入 #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

输入 #2

1 1
1000000000
2 1 1

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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 翻译