分数: 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