103435: [Atcoder]ABC343 F - Second Largest Query

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:7 Solved:0

Description

Score: $525$ points

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

Input

Output

得分:$525$分

问题描述

给你一个长度为$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

加入题单

上一题 下一题 算法标签: