← 返回题目列表

AtCoder · abc343_f

I. 第二大查询

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

给你一个序列 A = (A_1, A_2, \ldots, A_N) 长度 N.

流程 Q 按给出的顺序进行查询。每个查询属于以下两种类型之一:

  • 类型 1:以表格形式给出 1 p x。改变值 A_p to x.
  • 类型 2:以表格形式给出 2 l r。打印 出现次数 第二大值 (A_l, A_{l+1}, \ldots, A_r)。更准确地说,打印整数的数量 i 满意 l \leq i \leq r 这样正好有一个不同的值大于 A_i 其中 A_l, A_{l+1}, \ldots, A_r.

约束

  • 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-th 查询并以下列格式之一给出:

1 p x
2 l r

输出

让 q 是类型的数量-2 查询。打印 q 行。 的 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) is 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