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)$ 中。更精确地，输出满足 $l \leq i \leq r$ 且在 $A_l, A_{l+1}, \ldots, A_r$ 中恰好存在一个与 $A_i$ 不同且大于 $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$

输出格式

设 $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

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 \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$ 查询。 所有输入值均为整数。最初，$A = (3, 3, 1, 4, 5)$。 对于第一个查询，$(3, 3, 1)$ 中的第二大值是 $1$，在 $3, 3, 1$ 中出现一次，因此输出 $1$。 对于第二个查询，$(5)$ 中不存在第二大值，因此输出 $0$。 第三个查询使得 $A = (3, 3, 3, 4, 5)$。 对于第四个查询，$(3, 3, 4)$ 中的第二大值是 $3$，在 $3, 3, 4$ 中出现两次，因此输出 $2$。

标签: AtCoder|abc343F

来源

AtCoder|abc343F