103435: [Atcoder]ABC343 F - Second Largest Query

Problem Statement

You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$.

Process $Q$ queries in the order they are given. Each query is of one of the following two types:

• Type $1$: Given in the form 1 p x. Change the value of $A_p$ to $x$.
• Type $2$: Given in the form 2 l r. print the number of occurrences of the second largest value in $(A_l, A_{l+1}, \ldots, A_r)$. More precisely, print the number of integers $i$ satisfying $l \leq i \leq r$ such that there is exactly one distinct value greater than $A_i$ among $A_l, A_{l+1}, \ldots, A_r$.

Constraints

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• For type-$1$ queries, $1 \leq p \leq N$.
• For type-$1$ queries, $1 \leq x \leq 10^9$.
• For type-$2$ queries, $1 \leq l \leq r \leq N$.
• There is at least one type-$2$ query.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$\text{query}_{1}$
$\vdots$
$\text{query}_{Q}$

Here, $\text{query}_{i}$ is the $i$-th query and given in one of the following formats:

$1$ $p$ $x$

$2$ $l$ $r$

Output

Let $q$ be the number of type-$2$ queries. Print $q$ lines. The $i$-th line should contain the response to the $i$-th type-$2$ query.

Sample Input 1

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

Sample Output 1

1
0
2

Initially, $A = (3, 3, 1, 4, 5)$.

For the first query, the second largest value in $(3, 3, 1)$ is $1$, which appears once in $3, 3, 1$, so print $1$.

For the second query, there is no second largest value in $(5)$, so print $0$.

The third query makes $A = (3, 3, 3, 4, 5)$.

For the fourth query, the second largest value in $(3, 3, 4)$, is $3$, which appears twice in $3, 3, 4$, so print $2$.

Sample Input 2

1 1
1000000000
2 1 1

Sample Output 2

0

Sample Input 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

Sample Output 3

0
1
0
2
4

问题描述

给你一个长度为$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$的整数$i$的数量，使得在$A_l, A_{l+1}, \ldots, A_r$中，恰好有一个不同于$A_i$的更大值。

约束条件

• $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$的查询。
• 所有的输入值都是整数。

输入

输入从标准输入给出，格式如下：

$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$行。其中$q$是类型$2$查询的数量。第$i$行应包含对第$i$个类型$2$查询的响应。

样例输入1

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

样例输出1

1
0
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$。

样例输入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